LeetCode刷题笔记一

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.

代码：

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i != s.length(); i++) 
        {
            if (dict[s[i]] > start)
                start = dict[s[i]];
            dict[s[i]] = i;
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
    }
};

思路解析：

对于一个字符串，若它的某个不重复的最长子串结束（假设以X结束），必然是由于X的下一个字符在该子串中出现过。假设不重复子串的第一个字符的前一个字符索引为start，则start往后的某个字符只要在start之后没有出现过，即可归入该不重复子串。

假设最多有256个不同的字符，dict数组用于记录字符串中某个字符上次出现时的位置（这里指在字符串中的索引值）。初始时，不重复子串的第一个字符就是字符串的第一个字符（即start为-1）；每个字符的dict数组值都为-1，表示在start之后还未出现过。依次迭代字符串中的每个字符，若字符(设索引为i)没有在start之后出现过，则可归入不重复子串，并记录在start之后出现的位置，放入dict[s[i]]；当某个字符在start之后第二次出现时，其dict数组值必然是大于start的，此时就表明一个不重复的最长子串出现，可比价该不重复子串与现有不重复子串的长度，更新最长不重复子串的信息。

寻找下一个不重复子串时，起始位置应当是导致上一个不重复子串结束的字符上一次出现的位置，当时它位于上一个不重复子串中。

复杂度：由于每个字符遍历一次，复杂度为O(n)。

总结：在查找一个字符串中的最长不重复子串时，第一个不重复子串可从字符串的第一个字符向后扩展，直到某个字符再次出现为止，设它为Y；下一个不重复子串应从Y上次出现位置之后开始扩展，以此类推。