Sliding Windows

Double pointer, fast pointer in front of the sweep, constantly put characters into the map, encounter repeated stop, slow pointer to the repeat element first appeared in the next position, continue operation. The key point is that

  • If I jumps to the next duplicate number, remember to delete the previous map; otherwise, the subsequent number will be affected.

2. The optimized version

Consider the example: kxabcabCBb

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int i = 0;
        int j = 0;
        int max = 0;
        while (j < s.length()) {
            The condition after && causes characters before the slow pointer to be ignored, saving time for remove
            if (map.containsKey(s.charAt(j)) && map.get(s.charAt(j)) >= i) {
                i = map.get(s.charAt(j)) + 1; // If repeated characters are encountered, close the left margin
                // j++; no
            } else {
                map.put(s.charAt(j), j);
                max = Math.max(max, j - i + 1);
                j++; // No duplicate characters are encountered, extend the right boundary}}returnmax; }}Copy the code

1. Unoptimized version

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Use to store characters and corresponding index values
        Map<Character, Integer> map = new HashMap<>();
        int i = 0;/ / pointer to slow
        int j = 0;/ / pointer
        int max = 0;// Maximum length
        while (j < s.length()) {
            // When the fast pointer encounters a repeated character, the slow pointer jumps to the position where the repeated value first appears +1
            // Then delete the map before the slow pointer position to prevent impact on the later
            if (map.containsKey(s.charAt(j))) {
                i = map.get(s.charAt(j)) + 1;
                for (int k = 0; k < i; k++) {
                    map.remove(s.charAt(k), k);// This will time out}}else {// When the fast pointer encounters no duplicate characters, the fast pointer ++ computs Max
                map.put(s.charAt(j), j);
                max = Math.max(max, j - i + 1); j++; }}returnmax; }}Copy the code