3. 無重復(fù)字符的最長子串

題目描述

給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3。

示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"，所以其長度為 1。

示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"，所以其長度為 3。

請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

算法思想

解法一：動態(tài)規(guī)劃
在做算法題的過程中，遇到最值問題首先還是往貪心和動態(tài)規(guī)劃上靠攏。這一題和 最長回文子串 的動態(tài)規(guī)劃解法如出一轍。
1）定義狀態(tài)：dp[i][j] 表示子串s[i, j]是否為無重復(fù)子串，且i < j
2）狀態(tài)轉(zhuǎn)移方程：s[i, j]是無重復(fù)子串的條件是：子串s[i+1, j]是無重復(fù)的且子串s[i+1, j]中不包含與s[i]重復(fù)的字符 或者 子串s[i, j-1]是無重復(fù)的且子串s[i, j-1]中不包含與s[j]重復(fù)的字符。
dp[i][j] = (dp[i+1][j] && s[i] ? s[i+1, j]) || (dp[i][j-1] && s[j] ? s[i, j-1])，其中符號?表示 "不屬于"
3）考慮邊界：i < j

解法二：滑動窗口
滑動窗口的解題方法是看了力扣官網(wǎng)上網(wǎng)友分享的解法，非常的給力，點擊這里查看這位網(wǎng)友的分享。

代碼實現(xiàn)

解法一：動態(tài)規(guī)劃*

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }

        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], true);
        }

        int maxLength = 1;
        for (int j = 1; j < len; j ++) {
            for (int i = 0; i < j; i++) {
                if ((dp[i + 1][j] && s.substring(i + 1, j + 1).indexOf(s.charAt(i)) == -1) && (dp[i][j - 1] && s.substring(i, j).indexOf(s.charAt(j)) == -1)) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }

                if (dp[i][j] && j - i + 1> maxLength) {
                    maxLength = j - i + 1;
                }
            }
        }

        return maxLength;
    }
}

時間復(fù)雜度O(n^2)
空間復(fù)雜度O(n^2)
說明：上面的代碼在力扣上提交后，會出現(xiàn)超過內(nèi)存限制的提示，說明了雖然DP能夠解決這一問題，但是并不是最優(yōu)的解法，而比較優(yōu)秀的解法就是采用滑動窗口來實現(xiàn)

解法二：滑動窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 定義集合來作為滑動窗口
        Set<Character> set = new HashSet<>();
        // left為滑窗左邊界，right為滑窗右邊界
        int left = 0, right = 0;
        int maxLength = 0;
        int len = s.length();
        while (left < len && right < len) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                maxLength = Math.max(maxLength, right - left + 1);
                right ++;
            } else {
                set.remove(s.charAt(left));
                left ++;
            }
        }
        return maxLength;
    }
}

時間復(fù)雜度O(n)
空間復(fù)雜度O(n)