3. Longest Substring Without Repeating Characters

problem description

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

example

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

algorithm thought

第三遍做这个题了，首先看到题目就觉得应该用快慢指针做。定义一个快指针，每次让快指针先走，快指针每走一步记录走过的字符。如果出现快指针走过的字符之前出现过一次，就让慢指针走。慢指针每走一步，擦除一个记录，如果擦出的刚好是快指针当前的字符，慢指针停止，又轮到快指针走。快指针每走一步计算一次快慢指针之差，最后返回最大的差值就行。

然而我看我第二次做的记录，发现第二次的方法更好(大概律是看discuss的)，每次不是记录出现的次数，而是记录字符的位置，每次碰到重复的可以直接跳转到相应的位置，而不是一次次慢慢走。

code

//快慢指针
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0)
            return 0;
        int head=1,last=0,res=1;
        vector<int> pos(256,0);
        pos[s[last]]++;
        while(head<s.size()){
            if(++pos[s[head++]]==2){
                while(true){
                    if(--pos[s[last++]]==1)
                        break;
                }
            }
            res=max(res,head-last);
        }
        return res;
    }
};

//直接记录位置
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left=-1;
        vector<int> pos(256,-1);
        int res=0;
        for(int i=0;i<s.size();++i){
            if(pos[s[i]]>left){
                left=pos[s[i]];
            }
            pos[s[i]]=i;
            res=max(res,i-left);
        }
        return res;
    }
};

algorithm analysis

首先分析快慢指针，快慢指针最坏情况是所有字符一样，最好情况是所有字符都不同。在输入为n的情况下，最坏情况需要运行2n次，最好情况需要运行n次。最好最坏都是O(n)的时间复杂度。

记录位置的方法:只有一个循环，不管什么清况都是运行n次，时间复杂度是O(n)。

综合来看还是第二种方法更好