描述 Description

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.

[Longest Substring Without Repeating Characters]

分析 Analysis

用一个hash table保存每个字符上一次出现过的位置。从前往后扫描，假如发现字符上次出现过，就把当前子串的起始位置start移动到上次出现过的位置之后——这是为了保证从start到i的当前子串中没有任何重复字符。同时，由于start移动，当前子串的内容改变，start移动过程中经历的字符都要剔除。

[LeetCode 第三题，Longest Substring Without Repeating Characters]

代码 Code

    class Solution {  
    public:  
        int lengthOfLongestSubstring(string s) {  
            int start = 0; // current start point of substring without dup  
            int maxlen = 0; // max length of substring found  
            int table[256]; // hash table for index of each char appeared  
            memset(&table, -1, sizeof(table));//初始化为-1
            for (int i = 0;i < 256;i++) table[i] = -1; // if char not present, index is -1  
            int len = s.length();  
            for (int i = 0;i < len;i++) {  
                if (table[s[i]] != -1) {  
                    while (start <= table[s[i]]) table[s[start++]] = -1;  
                }  
                if (i - start + 1 > maxlen) maxlen = i - start + 1;  
                table[s[i]] = i;  
            }  
            return maxlen;  
        }  
    };

int main() {
    int res;
    char *_s;
    _s = (char *) malloc(512000 * sizeof(char));
    scanf("\n%[^\n]", _s);

    res = lengthOfLongestSubstring(_s);
    printf("%d\n", res);

    return 0;
}