Cpp code with 12ms runtime(dynamic programming)


  • 2
    8
     //the max length ended at index i is either i-j or Ans(i-i)+1,j is the index of last appearance of the same
    //character as S[i] ans Ans is the max length that ended at position i. This is the basic idea of this solution
    #include<algorithm>
    #include<cstring>
    class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
        int last[300];
        int len=s.length();
        if(len==0) return 0;
        int temp=1;
        memset(last,-1,sizeof(last));
        int ans=1;
        last[s[0]]=0;//mark down the last appearance of the same character
        for(int i=1;i<len;i++)
        {
            int lastApp=last[s[i]];
            if(lastApp==-1) temp++;
            else temp=min(temp+1,i-lastApp);
            last[s[i]]=i;
            ans=max(ans,temp);
        }
        return ans;
       }
    };

  • 0
    S

    hi, i tried your code. it is really fast! could you please explain how it works? Thanks a lot!


Log in to reply
 

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