描述

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

分析

假设在第 j-1 轮,已经找到了长度为 j-i 的不重复字串,接下来判断 j 是否在下标 ij-1 中存在相同的字符,若不存在,则更新不重复长度为 j-i+1;若存在重复,则设置 i=k+1 并更新不重复子串长度为 j-k。在下一轮判断 j+1 是否重复时,只需从 k+1 遍历到 j 即可。遍历字符串的复杂度为 $$\mathcal{O}(n)$$,遍历子串的复杂度为 $$\mathcal{O}(m)$$,因此整体的时间复杂度为 $$\mathcal{O}(n^2)$$,空间复杂度为 $$\mathcal{O}(1)$$。

最长子字符串.jpg

int lengthOfLongestSubstring(char* s) {
    int longest = 1, sublong = 1;
    int i = 0, j = 0;
    if (!s[0])
        return 0;
    while(s[++j]) {
        for (int k = i; k < j; k++) {
            if (s[j] == s[k]) {
                longest = longest > sublong ? longest : sublong;
                i = k + 1;
                sublong = j - i;
                break;
            }
        }
        sublong++;
    }
    longest = longest > sublong ? longest : sublong;
    return longest;
}

结果

Runtime: 12 ms, faster than 89.94% of C online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 12.5 MB, less than 83.11% of C online submissions for Longest Substring Without Repeating Characters.

优化

我们在第一种方法的基础上,通过牺牲空间换取时间的方式,建立一张映射表,映射表的键为字符,值为该字符上一次出现的位置,则可以将时间复杂度降到 $$\mathcal{O}(n)$$,已知字符的数量有限(256个),因此建立映射表的空间开销是固定的,所以空间复杂度为 $$\mathcal{O}(1)$$。

int lengthOfLongestSubstring(char* s) {
    int x[256] = { -1 };    // can not set to -1 on some compiler
    for (int i=0; i<256; i++) x[i] = -1;
    int longest = 0, pos = -1, i = -1;
    while(s[++i]) {
        pos = x[s[i]] > pos ? x[s[i]] : pos;
        x[s[i]] = i;
        longest = longest < (i-pos) ? i-pos : longest;
    }
    return longest;
}

结果

Runtime: 12 ms, faster than 89.94% of C online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 12.4 MB, less than 96.62% of C online submissions for Longest Substring Without Repeating Characters.