【LeetCode】【0003】Longest Substring Without Repeating Characters

描述

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 是否在下标 i 到 j-1 中存在相同的字符，若不存在，则更新不重复长度为 j-i+1；若存在重复，则设置 i=k+1 并更新不重复子串长度为 j-k。在下一轮判断 j+1 是否重复时，只需从 k+1 遍历到 j 即可。遍历字符串的复杂度为 ，遍历子串的复杂度为 ，因此整体的时间复杂度为 ，空间复杂度为 。

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.

---

优化

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

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.