3. Longest Substring Without Repeating Characters

LeetCode

Dynamic Programming

所谓“连续无重复子串”其实就是“连续无重复子序列”，相比于《674. Longest Continuous Increasing Subsequence》，无非就是把条件换成了“无重复”，所以我们可以尝试套用之前的思路。

设f[i]为：以a[i]结尾的最长连续无重复子串的长度。因为以a[i]结尾的最长连续子串是无重复的，所以以a[i - 1]结尾的最长连续子串也是无重复的。

我们知道对于数组的下标有begin + len(array) - 1 = end，因此有begin = end - len(array) + 1。以a[i - 1]结尾的连续子串的end = i - 1且len(array) = f[i - 1]，所以它的范围是[i - f[i - 1], i - 1]。

因此可得状态转移方程：

  • f[i] = max{ f[i - 1] + 1 }（如果a[i]在a[i - f[i - 1]]到a[i - 1]中没有重复)
  • f[i] = i - k（如果a[i]和a[k]重复，其中k的取值范围是[i - f[i - 1], i - 1]）
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        int f[] = new int[s.length()];
        f[0] = 1;
        int largest = f[0];
        for (int i = 1; i < s.length(); i++) {
            int curr = s.charAt(i);
            int k = i - f[i - 1] - 1;
            for (int j = i - 1; j >= i - f[i - 1] && j >= 0; j--) {
                if (curr == s.charAt(j)) {
                    k = j;
                    break;
                }
            }
            f[i] = i - k;
            largest = Math.max(largest, f[i]);
        }
        return largest;
    }
}

（注：本解法大篇幅参考了知乎作者“澪同学”的题解。）

Sliding Window

用Hashmap记录begin和end维持的窗口内每个字符出现的次数。遍历字符串，每访问一个字符有两部分操作。第一部分，判断窗口前沿元素s[end]是否出现过，向前移动前沿。第二部分，如果移动窗口前沿过程中发现有元素重复，向前移动窗口后沿，去除重复元素。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() == 0) {
            return 0;
        }
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int repeat = 0;
        int maxLen = 0;
        while (right < s.length()) {
            char r = s[right];
            window[r]++;
            if (window[r] > 1) {
                repeat++;
            }
            right++;

            while (repeat > 0) {
                char l = s[left];
                if (window[l] > 1) {
                    repeat--;
                }
                window[l]--;
                left++;
            }
            maxLen = max(maxLen, right - left);
        }
        return maxLen;
    }
};

最后，这类substring问题有一个通用模板，遇到substring问题可以尝试套用：

/*
	1. hashmap: elements frequency counting
	2. two pointers: size
	3. condition variable: (in this problem is "no repeat")
	
	while (end < s.length()) {
		if (hash[end] meets requirement) {
			modify condition variable
		}
		while (condition variable meets condition) {
			places for min size of substring
			if (hash[begin] meets requirement) {
				modify condition variable
			}
		}
		places for max size of substring
	}
	
*/

参考资料