C++ O(n) solution with clear explanation


  • 0
    S
    /*
       Use left pointer i and right pointer j.
       When we met s[j] which is already between [i,j], we update left pointer i.
       And what we need finally is return the max of j-i
    */
    class Solution {
    public:
    	int lengthOfLongestSubstring(string s) {
    	  unordered_map<char, int> charMap;
    	  int maxLen = 0, i, j;
    	    for(i=0, j=0; j<s.size(); j++) {
                  //Update left pointer and update maxLen
                  if(charMap.find(s[j]) != charMap.end() && charMap[s[j]] >= i) {
    	        maxLen = maxLen > (j-i) ? maxLen : (j-i);
    		i = charMap[s[j]] + 1;
    	      }
    
    	      charMap[s[j]] = j;
    	    }
    
               return maxLen > (j-i) ? maxLen : (j-i);;
    	}
    };
    

Log in to reply
 

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