Longest Substring Without Repeating Characters (双指针扫描) 【口试算法leetcode】

Longest Substring Without Repeating Characters (双指针扫描) 【面试算法leetcode】

题目：

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

题意在原串中找到最长的每个字母最多出现一次的字符串

做过类似的题，这种情况最好的做法就是用双指针对原串扫描，能在线性的时间解决。

i表示满足条件的字符串的起始位置，j表示结束位置。

j每次往前移动一次，遇到一个新的字符元素，判断当前的集合中是否已经存在这个字母，如果存在，移动i指针，直到排除之前出现过的这个元素。

类似贪心的思想，两个指针维护了以j结束的最长的满足条件的字符串，因此能得到最优解。

这中算法同样能够解决类似的题目例如每种元素最多出现n次的字符串，只需要用sign数组记录出现的次数并判断。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i,j,len=0,maxx=0;
        bool sign[30];
        memset(sign,0,sizeof(sign));
        for(i=0,j=0;j<s.length();++j)
        {            
            while(sign[s[j]-'a']==1)
            {
                sign[s[i]-'a']=0;
                ++i;                    
            }
            sign[s[j]-'a']=1;            
            maxx=max(maxx,j-i+1);
        }
        return maxx;
    }
};