DP java solution O(n) time complexity


  • 10
    O
    public int lengthOfLongestSubstring(String s) {
      if (s.length()==0) return 0;
         //keep a hashmap which stores the characters in string as keys and their positions as values
         HashMap<Character, Integer> map = new HashMap<Character, Integer>();
         int max=0;
         for (int i=0, j=0; i<s.length(); ++i){
               if (map.containsKey(s.charAt(i))){
     //if found in hashmap that value,then update j i.e pointer to the right of the same character last found.
                j = Math.max(j,map.get(s.charAt(i))+1);  
               }
    //else put in map and get max pointer update with the current longest string
              map.put(s.charAt(i),i);
              max = Math.max(max,i-j+1);
          }
    return max;
    }

  • 0
    N

    does this works correctly?
    if I have a string jabjcdel, it will give wrong ans.


  • 0
    O

    nope,i run my code on the same input : jabjcdel and it gave me the ans 7 i.e true! so i think code is running perfectly!


Log in to reply
 

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