int lengthOfLongestSubstring(char* s) {
int maxLen = 0, prevMaxLen = 0, prevIndexOf[128];
bzero(prevIndexOf, sizeof(prevIndexOf));
for (char *c = s; *c; c++) {
int idx = c  s + 1; // Add 1 to the index since prevIndexOf is initialized with zeros
int candidateLen = idx  prevIndexOf[*c];
int curMaxLen = (++prevMaxLen < candidateLen) ? prevMaxLen : candidateLen;
prevIndexOf[*c] = idx;
if (curMaxLen > maxLen) {
maxLen = curMaxLen;
}
prevMaxLen = curMaxLen;
}
return maxLen;
}
C solution, 3ms


Thanks @JasonZWJ
This was inspired by Kadane's algorithm for the maximal subarray problem.
The basic idea is that the length of the longest substring ending at positioni
is the lesser of length(longest substring ending at position
i  1
) + 1 i  prevIndexOf[*c]
i.e. the number of characters since the previous occurrence of the character at positioni
So we can use the longest substring length at each position and to compute the length at the succeeding position. It's convenient to initialize the
prevIndexOf
array with zeros, so the index computations have to be offset by one to account for that.
 length(longest substring ending at position