Question

Formatted question description: https://leetcode.ca/all/3.html


3. Longest Substring Without Repeating Characters

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

For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

Algorithm

If you give the example “abcabcbb” in an example, let you manually find the substring without repeated characters.

I will traverse one character by character, such as a, b, c, and then another a appears, then the first occurrence of a should be removed at this time, and then afterward, another b appears, then Remove the one occurrence of b, and so on, and finally find that the longest length is 3.

Therefore, it is necessary to record the characters that have appeared before. There are many ways to record. The most common is to count the number of characters, but the position of the character in this question is very important, so you can use HashMap to establish the character and its appearance. Mapping between.

Considering further, since the characters will appear repeatedly, should we save all occurrences or just record one location? The method we derive manually before is actually to maintain a sliding window, in which there are no repeated characters, and the size of the window needs to be enlarged as much as possible. Since the window is constantly sliding to the right, it only cares about the last position of each character and establishes a mapping.

The right border of the window is the position of the character currently traversed. In order to find the size of the window, a variable left is needed to point to the left border of the sliding window. In this way, if the character currently traversed has never appeared, the right border is directly expanded If it has appeared before, then it can be divided into two situations. It is in or not in the sliding window. If it is not in the sliding window, then it is fine. The current character can be added in. If it is, you need to remove this already in the sliding window. The characters that have appeared, the method of removing it does not need to traverse the left boundary left one by one to the right. Since the HashMap has saved the last position of the repeated character, it is enough to move the left pointer directly. Maintain a result res, and update the result res with the window size that has appeared, and you can get the final result.

Here you can create a HashMap to create a mapping between each character and its last appearance position, and then you need to define two variables res and left, where res is used to record the length of the longest non-repeated substring, and left points to the non-repeated substring The previous one of the starting position on the left of the string, because it is the previous one, so the initialization is -1, and then traverse the entire string, for each traversed character, if the character already exists in the HashMap, and if its mapping value If it is greater than left, then update left to the current mapping value. Then the mapping value is updated to the current coordinate i, which ensures that left is always the previous position of the current boundary, and then when calculating the window length, use i-left directly to update the result res.

Here is an explanation of the two conditions m.count(s[i]) && m[s[i]]> left in the if conditional statement in the program, because once the current character s[i] has been mapped in the HashMap, it means that the current The character of has already appeared, and if m[s[i]]> left is true, it means that the character that appeared before is in the window. If you want to add the current repeated character, you must remove the previous one, so Let left be assigned to m[s[i]], since left is the previous position of the left border of the window (this is also the reason left is initialized to -1, because the left border of the window is traversed from 0), so it is equivalent to having moved Remove the sliding window. For the simplest example “aa”, when i=0, a mapping of a->0 is established, and the result res is updated to 1, then when i=1, a is found in the HashMap and the mapping The value 0 is greater than -1 for left, so at this time, left is updated to 0, and the mapping pair is updated to a->1, then at this time i-left is still 1, without updating the result res, then the final result res is still 1, which is correct.

Code

Java

import java.util.HashMap;


public class Longest_Substring_Without_Repeating_Characters {

    public static void main(String[] args) {

    	Longest_Substring_Without_Repeating_Characters out = new Longest_Substring_Without_Repeating_Characters();
        Solution s = out.new Solution();
        int longest = s.lengthOfLongestSubstring("abcbefg");

        System.out.println(longest);
    }

    // ref: https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/
    class Solution_map {
        public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }

            int result = 0;
            HashMap<Character, Integer> hm = new HashMap<>();

            for (int left = 0, right = 0; right < s.length(); right++) {
                char probeChar = s.charAt(right);
                if (hm.containsKey(probeChar)) {
                    // mast max check i
                    // example "abba", last 'a' will result in index 0 if not max checking
                    left = Math.max(left, hm.get(probeChar) + 1);
                }
                hm.put(probeChar, right);
                result = Math.max(result, right - left + 1);
            }

            return result;
        }
    }

    // @note: remove the final check outside while loop, cleaner code, run time: 7ms. above method 16ms
    /*
     * optimization is:
     * 1. moving longest recording after
     * 2. no extra operation: removing first repeated char in inner while, then adding this char to set next looping
     * 3. "Math.max(j - i + 1, maxLen)" is cleaner than "x>y ? x:y"
     *
     */
    class Solution {
        public int lengthOfLongestSubstring(String s) {

            if (s == null || s.length() == 0) {
                return 0;
            }

            int l = 0; // left
            int r = 0; // right

            int result = 0;
            boolean[] isFoundInWindow = new boolean[256];

            while (r < s.length()) {

                while (isFoundInWindow[s.charAt(r)]) {
                    isFoundInWindow[s.charAt(l)] = false;
                    l++;
                }

                isFoundInWindow[s.charAt(r)] = true;

                // check before shrink
                result = Math.max(result, r - l + 1);

                r++;
            }

            return result;
        }
    }

}

All Problems

All Solutions