3. Longest Substring Without Repeating Characters - jiejackyzhang/leetcode-note GitHub Wiki

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

String类题目

采用sliding window的思想来解。用HashSet来保存当前window [left,right) 的character，如果s[right]不在其中，则可以继续将right向右扩展，若s[right]是重复字符，则将left向左移动以去掉重复元素。

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

注意到以上方法left和right都是一步一步的移动，时间复杂度为O(2n)，若可以直接定位left，则可以优化性能。 采用HashMap来记住前面字符的位置，则当发现重复字符时，可直接跳过前面的重复字符。 这里需注意的一点是若之前的重复字符在当前left的左边，则left应仍为当前的值。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0, left = 0, right = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(; right < s.length(); right++) {
            if(map.containsKey(s.charAt(right))) {
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            }
            ans = Math.max(ans, right-left+1);
            map.put(s.charAt(right), right);
        }
        return ans;
    }
}
⚠️ **GitHub.com Fallback** ⚠️