[LeetCode] 3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Example 4:
Input: s = “”
Output: 0

Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

最长无重复字符的子串。

思路

题意是给一个 input 字符串，请输出其最长的，没有重复字符的子串的长度。这是two pointer追击型指针/sliding window的基础题。

思路是用一个 hashmap 或者 hashset 以及两个指针 i 和 j，其中 i 指针在左边，j 指针在右边，j 指针每次看当前遍历到的 character 是否在 hashset 中出现过，此时有两种情况

• 如果没出现过则将当前这个字符串加入 hashset 并且 j++，同时每次更新一下此时此刻两个指针之间的距离 res，这就是满足题意的子串的长度
• 如果出现过则将 i 指针指向的字母从 hashset 中删除并且 i++

复杂度

时间O(n)
空间O(n) - hashset

代码

Java实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int i = 0;
        int j = 0;
        int res = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (!set.contains(c)) {
                set.add(c);
                i++;
                res = Math.max(res, i - j);
            } else {
                set.remove(s.charAt(j));
                j++;
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let map = {};
    let res = 0;
    let i = 0;
    let j = 0;
    while (j < s.length) {
        if (map[s[j]]) {
            map[s[i]] = false;
            i++;
        } else {
            map[s[j]] = true;
            res = Math.max(res, j - i + 1);
            j++;
        }
    }
    return res;
};

相关题目

3. Longest Substring Without Repeating Characters
1695. Maximum Erasure Value