Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

 https://oj.leetcode.com/discuss/13336/shortest-o-n-dp-solution-with-explanations

The key is to use a vector of 256 int to be hashmap and use i-startIdx+1 to denote the length of the string.

从左往右扫描，当遇到重复字母时，以上一个重复字母的index+1，作为新的搜索起始位置，

直到最后一个字母，复杂度是O(n)。

 

 

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len=s.length();
       
        vector<int> v(256,-1);
        int ret=0, startIdx=0;
       
        for (int i=0; i<len; i++)
        {
            int j=s[i];
            startIdx = max(v[j]+1,startIdx);
            v[j]=i;
            ret = max(ret,i-startIdx+1);
        }
       
        return ret;
    }
};