My O(n) solution in 72 ms


  • 3
    C
    int lengthOfLongestSubstring(string s) {
            int longestLength = 0, tempLength = 0, i = 0;
            int size = s.size();
            int findTable[256];
            for(int k = 0; k < 256; k++)
                findTable[k] = -1;
            while(i < size)
            {
                if(tempLength + size - i <= longestLength)
                    return longestLength;
                    
                char c = s[i];
                int foundIndex = -1;
                if((foundIndex = findTable[c]) == -1 || foundIndex < i - tempLength)
                {
                    tempLength++;
                }
                else
                {
                    longestLength = longestLength > tempLength ? longestLength : tempLength;
                    tempLength = i - foundIndex;
                }
                findTable[c] = i;
                i++;
            }
            return longestLength > tempLength ? longestLength : tempLength;
        }

Log in to reply
 

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