003 - Longest Substring Without Repeating Characters

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.

Hide Tags

Hash Table Two Pointers String

Hide Similar Problems

(H) Longest Substring with At Most Two Distinct Characters

 

用一个256个int的数组辅助统计重复出现的字母，初始化为 -1，

如果出现了就存放该字母在字符串中的下标，遇到大于 –1 的就是重复出现的字母了。

至于这个重复出现的字母是否影响统计，需要一个辅助的变量来表示从哪里算起，

所以用了一个start，每当确认是有影响的重复字母，

就把该字母上次出现的下标，也就是辅助数组里存的那个下标，更新为新的起点（但不包括它），

    同时把统计值重置为 当前下标减去上次出现的下标，也就是从新起点之后的字母到现在的自己；

但如果新发现的重复字母，其辅助数组里存的上一次出现的下标，早于这个start，就不用更新了，

    因为起点之后并不包括该字母，应该视同第一次出现，直接将统计值sum++。

更新了sum之后，检查是否大于最终的结果total，如果是则更新total。

从头走到尾，一遍即可完成处理。

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int pre=-1, start=-1, idx=-1;
        int sum=0, total=0, len=s.length();

        array<int, 256> taken;
        taken.fill(-1);         //辅助数组全部初始化为 -1，
                                //不要用 int taken[256]={-1}; 这只能初始化第一个！！

        for(int ii=0; ii<len; ++ii)
        {
            idx = s[ii];
            pre = taken[idx];   //上一次出现的下标
            taken[idx] = ii;    //更新记录为本次出现的下标

            if(pre>start)       //在start之后，会影响统计结果
            {
                sum = ii - pre; //重算sum
                start = pre;    //更新起点
            }
            else
                sum++;

            if(total < sum)
                total = sum;
        }
        return total;
    }
};

16 ms.