LeetCode #3 Longest Substring Wi

Problem Specs:

Solution(Implemented in C):

/**
 * Abstract: I stole from the KMP substring search algorithm the idea of 
 * never-back-up-i(the text pointer) and came up with this solution; the key idea 
 * is to remember the location of the last occurence of every character(with an
 * aux-array a[], see FOOTNOTE) so as to avoid starting "all over again" when 
 * encountering a repetition(and within the "current longest subtext", that's why 
 * the clear() function uses a[s[i]] as an "sentinal" to guard against the clearance).
 * With this parenthesis the code should be clear and (hopefully) easy to understand. 
 * The figure below might help grasp this idea:
 * 
 *             |←-------- t --------→.........
 *             ↓                     
 * s:.........XA.....................X
 *            ↑                      ↑
 *         a[s[i]]                   i   
 *  
 * Running time of this solution is O(n) = cn, where n denotes the length of the text 
 * and c ranges from 1 to 256 with an average value much less than   the upper
 * bound(hopefully).
 * FOOTNOTE:The aux-array is used to provide an O(1) running time access to infomation
 * that's keyed(indexed, or associated with) characters; in C, an array of size 256(the
 * number of different characters that can be represented) is exactly the choice; for
 * larger charactor set(say, unicode) in other languages that's more advanced(say Java),
 * char[]'s not an opt; under such circumstance, a hash map's a natural choice.
 * 
 * NOTE:As always test client main() takes the input text from one of its arguments.
 */

void clear(int a[], int n, int t) { for (int i = 0; i < n; i++) { a[i] = (a[i] <= t) ? -1 : a[i]; } }

int lengthOfLongestSubstring(char * s){
    if (s == NULL || *s == '\0') return 0;
    int n = strlen(s);
    int a[256];
    for (int i = 0; i < 256; i++) { a[i] = -1; }
    int len = 1, t = 0;
    for (int i = 0; i < n; i++) {
        if (a[s[i]] == -1) {
            t++;
        } else {
            len = t > len ? t : len;
            t = i - a[s[i]];
            clear(a, 256, a[s[i]]);
        }
        a[s[i]] = i;
    }
    return len > t ? len : t;
}

int main(int argc, char *argv[]) {
    printf("%i\n", lengthOfLongestSubstring(argv[1]));
    return 0;
}