字符串 - 最长无重复子串的长度

3. 无重复字符的最长子串

题目描述

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

算法思想

解法一：动态规划
在做算法题的过程中，遇到最值问题首先还是往贪心和动态规划上靠拢。这一题和最长回文子串的动态规划解法如出一辙。
1）定义状态：dp[i][j] 表示子串s[i, j]是否为无重复子串，且i < j
2）状态转移方程：s[i, j]是无重复子串的条件是：子串s[i+1, j]是无重复的且子串s[i+1, j]中不包含与s[i]重复的字符或者子串s[i, j-1]是无重复的且子串s[i, j-1]中不包含与s[j]重复的字符。
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

解法二：滑动窗口
滑动窗口的解题方法是看了力扣官网上网友分享的解法，非常的给力，点击这里查看这位网友的分享。

代码实现

解法一：动态规划*

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;
    }
}

时间复杂度O(n^2)
空间复杂度O(n^2)
说明：上面的代码在力扣上提交后，会出现超过内存限制的提示，说明了虽然DP能够解决这一问题，但是并不是最优的解法，而比较优秀的解法就是采用滑动窗口来实现

解法二：滑动窗口

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;
    }
}

时间复杂度O(n)
空间复杂度O(n)