Cpp code with 12ms runtime(dynamic programming)

  • 2
     //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
    class Solution {
    int lengthOfLongestSubstring(string s) {
        int last[300];
        int len=s.length();
        if(len==0) return 0;
        int temp=1;
        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);
        return ans;

  • 0

    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.