Dynamic Programming解法

所謂“連續(xù)無重復(fù)子串”其實(shí)就是“連續(xù)無重復(fù)子序列”，相比于《674. Longest Continuous Increasing Subsequence》，無非就是把條件換成了“無重復(fù)”，所以我們可以嘗試套用之前的思路。

設(shè)f[i]為：以a[i]結(jié)尾的最長連續(xù)無重復(fù)子串的長度。因?yàn)橐?code>a[i]結(jié)尾的最長連續(xù)子串是無重復(fù)的，所以以a[i - 1]結(jié)尾的最長連續(xù)子串也是無重復(fù)的。

我們知道對于數(shù)組的下標(biāo)有begin + len(array) - 1 = end，因此有begin = end - len(array) + 1。以a[i - 1]結(jié)尾的連續(xù)子串的end = i - 1且len(array) = f[i - 1]，所以它的范圍是[i - f[i - 1], i - 1]。

因此可得狀態(tài)轉(zhuǎn)移方程：

• f[i] = max{ f[i - 1] + 1 }（如果a[i]在a[i - f[i - 1]]到a[i - 1]中沒有重復(fù))

• f[i] = i - k（如果a[i]和a[k]重復(fù)，其中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;
    }
}

（注：本解法大篇幅參考了知乎作者“澪同學(xué)”的題解。）

滑動窗口解法

用Hashmap記錄begin和end維持的窗口內(nèi)每個字符出現(xiàn)的次數(shù)。遍歷字符串，每訪問一個字符有兩部分操作。第一部分，判斷窗口前沿元素s[end]是否出現(xiàn)過，向前移動前沿。第二部分，如果移動窗口前沿過程中發(fā)現(xiàn)有元素重復(fù)，向前移動窗口后沿，去除重復(fù)元素。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() == 0) {
            return 0;
        }
        unordered_map<char, int> hash;
        int begin = 0, end = 0;
        int repeat = 0;
        int max_length = 0;
        while (end < s.length()) {
            if (hash[s[end]] > 0) {
                repeat++;
            }
            hash[s[end]]++;
            end++;
            
            while (repeat > 0) {
                if (hash[s[begin]] > 1) {
                    repeat--;
                }
                hash[s[begin]]--;
                begin++;
            }
            
            if (end - begin > max_length) {
                max_length = end - begin;
            }
        }
        return max_length;
    }
};

最后，這類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
    }
    
*/

參考資料

• 【每日一題：小Fu講解】LeetCode 3. Longest Substring Without Repeating Characters

• O(n) time O(1) space solution using Kadane's algo in Java