2Pointers+HashMap Brain-friendly Java Solution


  • 0

    The key points of this question:
    Step 1. Contiguous substring; two pointers: slow stands at the index where you first find the unique character; keep moving the fast pointer. Using a HashMap to check if there is repeat from slow to fast.
    Step 2. Non-repeating: every time there is a repeating character, we need to reset both of the pointers to the (previous slow pointer + 1).
    Step 3. At Step2, we also clear the HashMap to start a new record.

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            if(s.length() == 0 || s == null){
                return 0; 
            }
            if(s.length() == 1) return 1; 
            Map<Character, Integer> map = new HashMap<>(25); 
            int slow = 0; 
            map.put(s.charAt(slow), 1);
            int fast = 1; 
            int newLength = 1; 
            int tempLen = 0; 
            while(fast < s.length()){
                if(map.containsKey(s.charAt(fast))){
                    tempLen = fast-slow;  
                    map.clear(); 
                    slow++;
                    fast = slow; 
                }
                else{
                    map.put(s.charAt(fast), 1); 
                    tempLen = fast-slow+1; 
                    fast++; 
                }
                newLength = Math.max(newLength, tempLen);
            }
            
            return newLength; 
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.