3 无重复字符的最长子串

🚀 相关链接

LeetCode 3 - 无重复字符的最长子串

📜 描述

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

💡 示例

示例 1

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

示例 2

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

示例 3

• 输入: s = "pwwkew"

• 输出: 3

• 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

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

📝 提示

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

💭 思路

使用 滑动窗口 的思想来解决这个问题：

1. 维护一个窗口，窗口的左边界和右边界分别用 l 和 r 表示。
2. 使用一个列表 list 来存储当前窗口中的字符。
3. 遍历字符串 s，如果当前字符 s[r] 不在 list 中，则将其加入 list 并扩展右边界 r。
4. 如果当前字符 s[r] 已经在 list 中，则移除 list 中的第一个字符并收缩左边界 l。
5. 在每次扩展或收缩窗口时，记录窗口的最大长度。

💻 代码实现

public int lengthOfLongestSubstring(String s) {
    List<Character> list = new ArrayList<>();
    int l = 0, r = 0, ans = 0;
    while (l <= r && r < s.length()) {
        if (l == r) {
            list.add(s.charAt(l));
            ans = Math.max(ans, list.size());
            r++;
        } else {
            Character c = s.charAt(r);
            if (list.contains(c)) {
                list.removeFirst();
                l++;
            } else {
                list.add(s.charAt(r));
                ans = Math.max(ans, list.size());
                r++;
            }
        }
    }
    return ans;
}