题目

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.

思路

引子：粗略看了下，最暴力的方法是分别遍历头尾，然后在头尾间判断重复，时间复杂度为O(n^4)。
第一种：思考改进的方法，尝试减少重复计算。一开始想的是动态规划，怎么都搞不出来（因为实在也不熟悉动态规划）。后来扫了眼题解，说因为单个子问题可以决定父问题，所以可以用贪心。就是在扫描的时候第一个指针不是简单递增，而是直接跳过上一个重复的字母。这样可以将时间复杂度降到O(n^2)。
第二种：再次看题解，发现可以记录每个字符上一次出现的位置，这样就减少了在判断重复时的扫描，使时间复杂度达到O(n)。

实现一

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i = 0, j = 0;
        int rlt = 0;
        while(j < s.length()){
            int flag=1;
            for(int m=i; m<j ;m++){
                if(s[m] == s[j]){
                    flag = 0;
                    i = m + 1;
                    j++;
                    break;
                }
            }
            if(flag == 1){
                if( j-i+1 > rlt){
                    rlt = j-i+1;
                }
                j++;
            }
        }
        return rlt;
    }
};

实现二

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        const int MAX_CHAR = 256;
        int pos[MAX_CHAR];
        for(int i=0; i<MAX_CHAR; i++){
            pos[i] = -1;
        }
        int i = 0, j = 0;
        int rlt = 0;
        while(j < s.length()){
            if(pos[s[j]] >= i){
                i = pos[s[j]] + 1;
            }
            else{
                if( j-i+1 > rlt){
                    rlt = j-i+1;
                }
            }
            pos[s[j]] = j;
            j++;
        }
        return rlt;
    }
};

思考

看了别人的代码，发现有以下可以改进
数组初始化为-1，可以使用

vector<int> last_occ(256, -1);

更方便