My O(n) Solution


  • 35
    H

    if only use DP, it's an O(n*n) solution, adding a map to get O(n).

    class Solution {
        public:
            int lengthOfLongestSubstring(string s) {
                if(s.size()<2) return s.size();
                int d=1, maxLen=1;
                unordered_map<char,int> map;
                map[s[0]]=0;
                for(int i=1;i<s.size();i++)
                {
                    if(map.count(s[i])==0 || map[s[i]]<i-d)
                        d++;
                    else
                        d= i- map[s[i]];
                    map[s[i]]=i;
                    if(d>maxLen)
                        maxLen = d;
                }
                return maxLen;
            }
        };

  • 14
    M

    So my code, which works in O(n):

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int[] occ = new int[256];
            
            int max = 0, counter = 0, start = 1;
            for (int i=0; i < s.length(); i++){
                char ch = s.charAt(i);
                if (occ[ch] >= start){
                    counter -= occ[ch] - start + 1;
                    start = occ[ch] + 1;
                }  
                occ[ch] = i+1;
                max = Math.max(max, ++counter);
            }
            
            return max;
        }
    }

  • 7
    R

    My java version.

        public class Solution {
        public int lengthOfLongestSubstring(String s) {
                if (s == null)
    				return 0;
    
    			Map<Integer, Integer> dictionary = new HashMap<Integer, Integer>();
    
    			int max = 0;
    			int length = 0;
    
    			for (int i = 0; i < s.length(); i++) {
    			    length++;
    			    //If found repeating character, check if the character is in the current substring.
    				if (dictionary.containsKey(s.codePointAt(i))&&length>(i-dictionary.get(s.codePointAt(i))))
    					length =i - dictionary.get(s.codePointAt(i);
    				//Get the longest substring.			
    				max = Math.max(length, max);
    				dictionary.put(s.codePointAt(i), i);
    			}
    
    			return max;
        }
    }
    

  • 0
    Y
    This post is deleted!

  • 10
    R

    My modification of the top C++ answer.

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
                if (s.size()==0)
    				return 0;
    
                int count=0, maxLen=0;
                unordered_map<char,int> map;
                for(int i=0;i<s.size();i++)
                {
                    count++;
                    //Check if the new character is repeated and in the current substring
                    if(map.count(s[i])!=0 && map[s[i]]>i-count)
                        count=i-map[s[i]];
                    //label the postion of current charactre
                    map[s[i]]=i;
    
                    if(count>maxLen)
                        maxLen = count;
                }
                return maxLen;
            
        }
    };

  • 5
    S

    A similar solution in python:

    class Solution:
        # @return an integer
        def lengthOfLongestSubstring(self, s):
            cache = {}
            start = end = 0
            max_length = 0
            
            while end < len(s):
                if s[end] in cache and cache[s[end]] >= start:
                    # the char `s[end]` exists in range [start, end),
                    # move start to the next char of prior `s[end]`
                    start = cache[s[end]] + 1
                
                # update the index with latest one
                cache[s[end]] = end
                end += 1
                
                max_length = max(max_length, end - start)
            
            return max_length

  • 0
    J

    what if Unicode characters?


  • 1
    J
    class Solution {
    public:
        // NOTE: The problem is NOT about "longest repeating substring".
        // In that case, "abcab" would return "ab" length = 2; but in
        // original question, it would return "abc" = 3;
        //
        int lengthOfLongestSubstring(string s) {
    
            // map char to its last known position in string s
            //
            unordered_map<char, int> map;
    
            // max length containing current char
            //   abcab
            //       ^, count = 2
            //
            int count = 0;
            
            int max_count = 0;
    
            for (int i=0; i < s.length(); i ++) {
                char c = s[i];
    
                if (map.count(c) == 0) {
                    // no match, e.g. "abc"
                    //                   ^
                    count++;
                }
                else {
                    // find a match
                    //           count
                    //  *x*abcx, 3->4
                    //  ***xbcx, 3->3
                    //  ***axcx, 3->2
                    //
                    int pos = map[c];
                    if (pos + count < i) { // case 3->4
                        count ++;
                    }
                    else if (pos + count == i) { // case 3->3
                        ; // do nothing
                    }
                    else { // case 3->2
                        count = i - pos;
                    }
                }
    
                if (count > max_count) {
                    max_count = count;
                }
                map[c] = i;
            }
            return max_count;
        }
    };

  • 0
    O

    elegant code! took a while to understand though


  • 0
    R

    Could I know which lines puzzle you ?


  • 0
    O

    if (dictionary.containsKey(s.codePointAt(i)))
    length = Math.min(length , i - dictionary.get(s.codePointAt(i)));
    The case where length > (i - dictionary.get(s.codePointAt(i))) was intuitive for me, it took me few examples to figure out the case where length < (i - dictionary.get(s.codePointAt(i))). For my own code, I used dictionary.clear as every time a repeating character is found, then re-add the characters after the repeating character and before the current i index.
    However this would cause more running time, therefore your solution is better.


  • 0
    J
    This post is deleted!

  • 0
    T
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts.


  • 0
    E

    great solution


  • 0
    T

    Unicode testcase is missed for this problem.


  • 0
    S

    the same idea and implementation, the core trick is maintain a sub string window with two pointers

    int lengthOfLongestSubstring(string s) {
                int n = s.size();
                if (n <= 1) return n;
                
                // maintain a window with two pointers 
                int d = 0, max = 0;
                unordered_map<char, int> hm;
                for (int i = 0; i < n; ++i) {
                     if(hm.count(s[i]) == 0 || hm[s[i]] < i - d)
                         ++d;
                     else
                         d = i - hm[s[i]];
                     hm[s[i]] = i;
                     if (d > max) max = d;
                }
                
                return max;
            }

  • 0
    Y

    My code:

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            if(s.length()<2) return s.length();
            int start=0,end=0,res=0;
            HashMap<Character,Integer> set=new HashMap<>();
            while(end<s.length()){
                if(set.keySet().contains(s.charAt(end))){
                    int ind=set.get(s.charAt(end));
                    if(ind>=start) start=ind+1;
                }
                set.put(s.charAt(end),end);
                res=Math.max(res,end-start+1);
                end++;
            }
           return res; 
        }
    }

  • 0
    S

    Really like the idea that "If found repeating character, check if the character is in the current substring." so that no need to manually clear the previous result. Thanks for sharing~!


  • 0
    D

    why not tell time?mine is 79ms

    class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
    if (s.size() <= 0)
    return 0;

                     int max_len = 1;
                     int note_map[s.size()];
                     memset(note_map, 0, sizeof(int)*s.size());
                     map<char, int> repeat_map;
                     map<char, int>::iterator iter;
    
                     note_map[0] = 1;
                     repeat_map[s[0]] = 0;
                     for (string::size_type i = 1; i < s.size(); i++){
                        int pre_len = note_map[i - 1];
                        iter = repeat_map.find(s[i]);
                        if (iter == repeat_map.end() || iter -> second < (i - pre_len)){
                            note_map[i] = pre_len + 1;
                        }else{
                            note_map[i] = i - (iter -> second);
                        }
                        repeat_map[s[i]] = i;
                        if (note_map[i] > max_len)
                            max_len = note_map[i];
                     }
    
                     return max_len;
       
    }
    

    };


Log in to reply
 

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