Java solution and explanation using HashMaps


  • 0
    R
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
           
          HashMap<Character,Integer> hm = new HashMap<Character,Integer>();
          
          int maxLen = 0;
          int start = 0;
          int end = 0;
          int currLen = 0;
          while(start<=end && end<s.length()){
              
              if(!hm.containsKey(s.charAt(end))){
                   
                   hm.put(s.charAt(end),end);
                   end++;
                   currLen++;
                   if(currLen>maxLen){
                       maxLen=currLen;
                   }
                   
              }
              else{
                  
                  if(hm.get(s.charAt(end))<start){
                      hm.put(s.charAt(end),end);
                      currLen++;
                      end++;
                       if(currLen>maxLen){
                       maxLen=currLen;
                   }
                  }
                  else{
                      start = hm.get(s.charAt(end))+1;
                      if(end<start){
                          end = start;
                      }
                      currLen = end-start;
                  }
              }
              
          }
          return maxLen;
        }
        
    }
    

    To start off, I'm keeping track of a current length and the maximum length of an already visited string without any repeating characters. The idea is to keep track of the last visited index of every character that has been visited. I'm doing this using a hashmap. There are three cases to consider:

    1. The current character is never visited, that means the hashmap doesn't contain this character.
      In this case, I simply increment the size of my current non repeating string i.e currLen by 1 and then check it against the maxLen. I also increment the end pointer of the current string.

    2. If the character is already visited, that means, it exists in the hashmap, there can be 2 conditions:

      i.The most recent occurance of this character lies outside the string i.e the character's latest index < start of the current string. In this case, I don't have to worry about any repetitions. I simply move my end pointer further and check the length against maxLen.

    ii. However, if the character does belong to the string, I move my start to the index after the character's last index, ensuring no repetitions again.


Log in to reply
 

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