Sword finger offer II 016 Longest substring without duplicate characters

Summary

Substring problem , The double pointer must be right ！

subject

Given a string s , Please find out that there are no duplicate characters in it Longest continuous substring The length of .

Ideas

Questions involving continuous characters or arrays , The first reaction is double pointer .

The right pointer moves to the left , We save every character Between the current left and right pointers First occurrence of subscript . When repeated characters appear , Determine whether the maximum length is between the left and right pointers and save . Then judge the subscript of the character for the first time , Then the left pointer jumps directly to the left of the character .

Pay attention to various boundary problems , Be careful .

solution

Code

public int lengthOfLongestSubstring(String s) {
    int left = 0;
    Map<Character, Integer> map = new HashMap<>();
    int maxLength = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        //  Encountered a duplicate character in the left and right pointers , Then judge the longest length , And move the left pointer to the new position 
        if (map.containsKey(c) && map.get(c) >= left) {
            maxLength = Math.max(maxLength, i - left);
            left = map.get(c) + 1;
        }
        //  The boundary processing of the right pointer moving to the last bit 
        if (i == s.length() - 1) {
            maxLength = Math.max(maxLength, i - left + 1);
        }
        //  No other issues need to be considered , Directly update the current string to the current subscript position 
        map.put(c, i);
    }

    return maxLength;
}