c++ one pass solution w/ explaination


  • 0
    2

    1 Using a map to record the positons of the letters in current substring.
    2 Renew the beginning of current string when duplicate letter is found.
    3* beware of duplicate letters that appeared before the current head.

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int result=0,cur=0,head=0;
            unordered_map<char,int> mp;
            
            for(int i=0;i<s.length();i++){
                if(mp.find(s[i])==mp.end()) {
                    mp[s[i]]=i;
                    cur++;
                }
                else{
                    head=max(mp[s[i]],head);
                    cur=min(i-mp[s[i]],i-head);
                    
                    mp[s[i]]=i;
                }
                result=(result>cur) ? result:cur;
            }
            
            return result;
        }
    };
    

Log in to reply
 

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