题目

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.

原题链接

解题思路

求解字符串中无重复元素的最长子串。解决本题的方法是记住当前元素在这之前最后一次出现的位置。具体请参考代码中的注释。

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if(n<=0)  return 0;
        // 记录字符最后一次出现的位置
        int table[256];
        for(int i=0;i<256; ++i)
            table[i] = -1;
        int max = 0;
        int RepeatIndex = -1;
        for(int i=0; i<n; ++i){
            //该字符在 i 和 RepeatIndex之间出现过，则更新RepeatIndex
            if(table[s[i]] > RepeatIndex){
                RepeatIndex = table[s[i]];
            }
            int len = i-RepeatIndex;
            if(len > max)  max = len;
            table[s[i]] = i;
        }
        return max;
    }
};