1.原題

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

2.題意

給定一個字符串，找出其最大的子串，子串不包含重復字符。

3.思路

• 首先，什么是子字符串，什么是子序列，子串代表的是原字符串中連續(xù)的字符，而子序列代表的是子序列不需要是挨著的，只要是在原字符串中也是這樣的先后順序。舉個例子，比如pwwkew，wke是子串，而pwke只是子序列
• 其次，題目的一個重要的要求是，子串中不能有重復元素
• 做法是，我們從第一個元素開始往后掃描，一邊掃描，一邊保存一個hash表，這個表記錄的是截止到當前的字符在原字符串中的位置（下標）。
• 當我們掃描到某個字符，發(fā)現(xiàn)該字符在上一個子串中已經(jīng)存在了，我們更新hash表中該字符的下標，并查看當前的子字符串是不是長度當前最大。
• 舉例，比如對于pwwkew，
  • 掃描p記錄p對應的下標p->0,
  • 掃描w同樣記錄w->1,
  • 繼續(xù)掃描時發(fā)現(xiàn)w已經(jīng)在上一個字符串中出現(xiàn)了，那么上一個字符串的長度就是2，更新下當前最大的子串長度到2.
  • 這個時候開啟了新的子串，
  • w的下標是w->2,
  • 然后掃描k：k->3,
  • 繼續(xù)，e->4，
  • 接下來又掃描發(fā)現(xiàn)了w，這個時候上一個子串到頭了，子串是wke，長度是3.更新當前最大的子串長度是3.

4.代碼如下

JAVA

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int begin_index = 0;
        int max = 0;
        int[] mark = new int[256];
        Arrays.fill(mark, -1);
        for(int i = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            if(mark[index] != -1 && mark[index] >= begin_index) {
                max = max > (i - begin_index)?max: i - begin_index;
                begin_index = mark[index] + 1;
            }
            mark[index] = i;
        }
        max = max > (s.length() - begin_index)?max: s.length() - begin_index;
        return max;
    }
}

Python

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        hash_table = []
        for i in range(256):
            hash_table.append(-1)
        max_res = 0
        begin_index = 0
        for i in range(len(s)):
            if hash_table[ord(s[i])] != -1 and hash_table[ord(s[i])] >= begin_index:
                max_res = max(max_res, i - begin_index)
                begin_index = hash_table[ord(s[i])] + 1
            hash_table[ord(s[i])] = i
        max_res = max(max_res, len(s) - begin_index)
        return max_res