[LeetCode 03] Longest Substring Without Repeating Characters

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.

Diffculty
Medium

Similar Problems
[LeetCode ] Longest Substring with At Most Two Distinct Characters Hard

Analysis

使用 hash 保存每次搜索过程中访问过的每个字符所在位置，只需记录一个标志 0 或 1 表示有没有访问过即可。

使用两个指针（或者 index ），第一个指针指向搜索起始位置，第二个指针表示当前所在位置， 如果第二个指针遇到了一个重复字符，计算一下当前已搜索的长度 (i - start)，与最长长度比较。 结束这次搜索，然后从这个重复字符第一次出现的位置的下一个字符开始下一次搜索。 这时候需要把这个重复字符第一次出现前所有的字符在 hash 表里 reset 成未访问过的状态。

注意：hash表 < 字符，字符串中所在位置 > 和 < 字符, 1 或 0 > 区别是： 前者可以直接定位重复字符第一次所在的位置，而后者必须通过 if(s[k] == s[cur_index]) 来判断。

int[26] for Letters 'a' - 'z' or 'A' - 'Z'
int[128] for ASCII
int[256] for Extended ASCII

Solutions

解法一

class Solution {
public:
    int lengthOfLongestSubstring(string s) { // Longest Substring Without Repeating Characters
        int ht[256] = {0}; // 用ht[s[i]] 记录s[i]是否出现过
        int max_len = 0;
        int start = 0;

        for(int i = 0; i < s.length(); ++i) {
            if(ht[s[i]] != 0){ // encounter a repeat
                max_len = max(max_len, i - start);

                // the loop update the new start point
                // and reset flag array
                //              0 1 2 3 4 5
                //              | | | | | |
                // for example, a c b c a b, when it comes to 2nd c,
                //              s     i
                // it update start(s) from 0 to 3, reset flag for all char before a[i]
                for(int k = start; k < i; ++k) {
                    if(s[k] == s[i]) { // c == c: k == 1, i == 3
                        start = k + 1; // get the index: start == 2
                        break;
                    }
                    else{
                        ht[s[k]] = 0; // reset flag for elments before s[k]
                    }
                }
            }
            else{ // not a repeat
                ht[s[i]]++;
            }
        }
        max_len = max((int)s.length() - start, max_len);

        return max_len;
    }
};

解法二

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        vector<int> bitmap(128, -1); // 用 bitmap[s[i]] 存s[i]在string中的位置
        int res = 0;
        int start = 0, lastStart = 0;
        for(int i = 0; i < n; i++) {
            if(bitmap[s[i]] != -1) { // 在 bitmap 中发现s[i]已经出现过(当前位置是i)
                res = max(res, i - start);
                lastStart = start;
                start = bitmap[s[i]] + 1;
                for(int j = lastStart; j < bitmap[s[i]]; j++) // 从start点遍历到s[i]第一次出现的位置,然后把这位置之前出现的字符都重置
                    bitmap[s[j]] = -1;
            }
            bitmap[s[i]] = i;
        }
        res = max(res, n - start); // 不要忘了最后的判断
        return res;
    }
};

解法三 优化版，当 s[i] 是一个在 [j, i) 范围中出现过的重复字符时，也即某个 k ∈ [j, i)，存在 s[k] == s[i]，我们不用从 j 开始一个个遍历直到 k，而是可以一次性略过 k 位置之前的所有字符，直接从 k + 1 的位置开始计算新的无重复字符字串。这就需要我们用一个 map<char, int> 来记录重复字符所在的位置，当然用 ht[s[i]] = i 也可以达到目的。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> um;               // um 记录遍历过程中每个字符最后出现的位置
        int res = 0;
        int start = 0; // start 记录当前不重复子串的起点，i 是当前位置

        for(int i = 0; i < s.length(); ++i){
            if(um.find(s[i]) != um.end() && um[s[i]] >= start) { // 如果出现了重复字符 s[i]
                start = um[s[i]] + 1;   // 更新 start
            } else {  // 如果当前维护的不重复子串中没有出现s[i]
                res = max(res, i - start + 1); // 更新结果，取较大者
            }
            um[s[i]] = i; // 更新 um
        }
        return res;
    }
};

算法时间复杂度 O(n)，空间复杂度 O(1)。因为 ASCLL 码字符个数 128 个， 这里用 unordered_map 打表记录每个字符在字符串中最后出现的位置， unordered_map 的空间消耗最大为128，所以时间复杂度是常数级的。 unordered_map的查找插入操作的时间复杂度都是 O(1)，所以整个算法的时间度为O(n)。 需要注意的是，unordered_map 是无序容器，在找是否出现重复字符的时候， 一定要在当前考察的子串的范围内查找，所以条件 && um[s[i]] >= j 不能漏。 当然这里也可以用一个 128 长度的数组代替 unordered_map 的功能，这样的好处是数组是有序的。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hs[128];
        int res = 0, i = 0, j = 0;
        memset(hs, -1, 128 * sizeof(int));

        while(i < s.size()){
            if(hs[s[i] - 0] >= j)
                j = hs[s[i] - 0] + 1;
            else
                res = max(res, i - j + 1);

            hs[s[i] - 0] = i;
            i++;
        }
        return res;
    }
};