DP java solution O(n) time complexity

  • 10
    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
              max = Math.max(max,i-j+1);
    return max;

  • 0

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

  • 0

    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.