Thanks the top voted 2 similar solutions


  • 0

    In summary, the similar idea is easy to implement but hard to AC.

    So where is the key points ?

    I think the key points is that we should check

      dict[s[i]] > start
    

    To update

      start=dict[s[i]] 
    

    Here are the top voted 2 similar solutions.

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int len=s.size();
            vector<int> dict(256, -1); 
            int result=0;
            int start=-1;
            for(int i=0; i<len; i++){
                if(dict[s[i]]>start)
                    start=dict[s[i]];
                dict[s[i]]=i;
                result=max(result, i-start);
            }
            return result;
        }
    };
    

    And another similar solution 2 just announce to use the DP method.

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int len=s.size();
            vector<int> dict(256, -1); 
            int result=0;
            int start=-1;
            for(int i=0; i<len; i++){
                start=max(start, dict[s[i]]);
                dict[s[i]]=i;
                result=max(result, i-start);
            }
            return result;
        }
    };

Log in to reply
 

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