3. Longest Substring Without Rep

题目描述

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

输入与输出

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};

样例

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.

题解与分析

解法一

暴力枚举每一个可能的起始位置，通过一个 bool 数组维护当前已经出现过的字符，当发现有重复字符出现时，更新最大长度，清空数组信息，检测下一个可能的起始位置。

C++ 代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxlen = 0;
        int curlen = 0;
        bool arr[256];
        int size = s.size();
        fill(arr, arr + 256, true);
        for (int i = 0; i < size; ++i) {
            for (int j = i; j < size; ++j) {
                if (arr[s[j]]) {
                    arr[s[j]] = false;
                    ++curlen;
                }
                else
                    break;
            }
            if (curlen > maxlen)
                maxlen = curlen;
            fill(arr, arr + 256, true);
            curlen = 0;
        }
        return maxlen;
    }
};

该解法的时间复杂度为 O(n^2)。

解法二

上述解法复杂度高达 O(n^2) 的原因是：每次枚举时并不能重复利用之前枚举时得到的信息，导致大量重复的判断。要想降低复杂度，必须想办法重复利用每次枚举获得的信息。

我们使用一个长度为256的 int 数组arr来记录当前每个 ascii 字符最后一次出现的位置，如果没有出现则为 -1 ；使用一个 int 变量curlen记录以上一个字符结束的最长不重复子串长度（下文简称上一子串）。

设当前字符为c，下面我们分情况讨论不同情况下如何利用arr与curlen变量更新以当前字符结束的最长不重复子串长度：

• 首先判断字符c是否出现过：
• arr[c] == -1，意味着字符c第一次出现，自然不可能与上一子串中的字符重复，因此更新curlen = curlen + 1。
• arr[c] != -1，表示字符c曾经出现过。
• 上一子串的起始位置为i - curlen，判定该位置与字符c上一次出现的位置的关系：
• i - curlen > arr[c]，即在字符c最后一次出现之后上一子串才开始，则本次出现的字符c不可能与上一子串中的字符重复，因此更新curlen = curlen + 1。
• i - curlen <= arr[c]，即字符c最后一次出现的位置在上一子串中，则以当前字符结束的最长不重复子串的起始位置应该在arr[c] + 1处（该处与当前字符之间不可能有第二个c，并且作为上一子串的子串，自身无重复），因此更新curlen = i - arr[c]。

C++ 代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxlen = 0;
        int curlen = 0;
        int arr[256];
        fill(arr, arr + 256, -1);
        for (int i = 0; i < s.size(); ++i) {
            curlen = i - curlen <= arr[s[i]] ? i - arr[s[i]] : curlen + 1;
            /* 上面一行等价于该注释区域代码
            if (arr[s[i]] == -1)
                ++curlen;
            else
                if (i - curlen > arr[s[i]])
                    ++curlen;
                else
                    curlen = i - arr[s[i]];
            */
            if (curlen > maxlen)
                maxlen = curlen;
            arr[s[i]] = i;
        }
        return maxlen;
    }
};

显而易见，该解法的时间复杂度为 O(n) ，相对解法一有很大进步。