O(n) Java solution with detailed explanation


  • 3
    R

    We use a HashMap to store characters and the corresponding updated index. Loop from the first character to the last character of the string. Everytime when a duplication is detected, the length is calculated by using the current index i minors the dupNextIndex, and the dupNextIndex is updated.

    For example, abcdbcdcd.
    At first dupNextIndex = 0, in the loop of second b, a duplication pairs b is detected, then dupNextIndex is set to be 2 (the next character of the first b). In the loop of second c, a duplication pairs c is detected, then dupNextIndex is set to be 3 (the next character of the first c), etc. When update dupNextIndex, note that we use dupNextIndex = Math.max(hash.get(c) + 1, dupNextIndex) instead of dupNextIndex = hash.get(c) + 1 to avoid that the dupNextIndex goes back.

    At last, we need to deal with the case when the longest substring is at the end of the string.

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            
            if (s == null || s.length() == 0)
                return 0;
            
            int maxLen = 1;
            int dupNextIndex = 0;
            HashMap<Character, Integer> hash = new HashMap<Character, Integer>();
    
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (hash.containsKey(c)) {                    
                    maxLen = Math.max(maxLen, i - dupNextIndex);
                    dupNextIndex = Math.max(hash.get(c) + 1, dupNextIndex);
                }
                hash.put(c, i);
            }
    
            maxLen = Math.max(maxLen, s.length() - dupNextIndex);
            
            return maxLen;
        }
    }

  • 0

    smart!
    reading your codes need to think carefully


Log in to reply
 

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