Longest_Substring.png
/**
* This is an improved version over the previous submission: https://www.jianshu.com/p/56eac9b1f73c
*/
void clear(int *a, char *s, int start, int end) { for (int i = start; i <= end; i++) { a[s[i]] = -1; } }
#define R 128//capacity of the character set
int lengthOfLongestSubstring(char * s) {
if (s == NULL || *s == '\0') return 0;
int n = strlen(s);
int *a = (int*)malloc(R * sizeof(*a));
for (int i = 0; i < R; i++) { a[i] = -1; }
int len = 0, start = 0;
for (int i = 0; i < n; i++) {
if (a[s[i]] != -1) {
int t = i - start;
if (len < t) { len = t; }
start = a[s[i]] + 1;
clear(a, s, i - t/*i - t = start*/, a[s[i]]);
}
a[s[i]] = i;
}
int t = n - start;
if (len < t) { len = t; }
return len;
}
