字符串的非重复子串

题目链接-来源：力扣（LeetCode）

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

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

思路：

子串类问题可以用双指针法降低一层复杂度。一个前指针 start 指向子串的开始，一个后指针 i 指向子串末端。用一个 max 更新子串最大长度，用一个哈希表记录 i 收集到的字符、下标 + 1键值对。当发生冲突时，若 start 的位置靠前，就移动到到冲突字符的键值处，否则不动，同时更新键值。注意，为什么 front 靠后时要保持不动？因为我们每次移动 start 的时候，并没有删除旧的键值对，也就是说，欲跳转前往的键值可能并不在当前子串中，因此我们要锁定当前 start 的位置让其只能前进不能后退，以免跳转到一个不在当前子串中的位置。待 end 遍历整个字符串，输出 max 即可获得长度。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> chars = new HashMap<>();
        int n = s.length();
        int maxLen = 0, start = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            start = Integer.max(start, chars.getOrDefault(c, 0));
            chars.put(c, i + 1);
            maxLen = Integer.max(maxLen, i - start + 1);
        }
        return maxLen;
    }
}