My accepted O(n) solution in C++


  • 1
    K
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) 
        {
            
            int max=0;
            for(int j=0;j<s.size();j++)
            {
                int HTable[256]={0};
                int len=0;
                int i=j;
                for(;i<s.size();i++)
                {
                    if(HTable[(int)s[i]]==0)
                    {
                        len++;
                        HTable[(int)s[i]]++;
                    }
                    else
                        break;
                }
                if(max<len)
                    max=len;
                if(s.size()==i)
                    break;
            }
            return max;
          
        }
    };

  • 0
    Q

    I think it is O(n2) solution


  • 0
    C

    Unfortunately this is O(n^2) as pointed. I proposed a solution O(n) which won't reset HTable[].
    Have a look here


Log in to reply
 

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