3. Longest Substring Without Rep

题目：

Given a string, find the length of the longest substring without repeating characters.

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

分析：

假设子串里含有重复字符，则父串一定含有重复字符，单个子问题就可以决定父问题，因此可以用贪心法。跟动规不同，动规里，单个子问题只能影响父问题，不足以决定父问题。
从左往右扫描，当遇到重复字母时，以上一个重复字母的index+1，作为新的搜索起始位置，直到最后一个字母，复杂度是O(n)。如下图所示。

Figure: 不含重复字符的最长子串

实现：

int lengthOfLongestSubstring(char* s) {
    
    //解法1：leet code time问题
    int num[128];
    int flag = 0;
    int maxLength = 0;
    int i;
    int tmp;
    memset(num, -1, 128*sizeof(int));
    for (i = 0; i < strlen(s); i++) {
        tmp = num[s[i]];
        num[s[i]] = i;  //存储出现的位置
        if (tmp >= flag) {
            maxLength = maxLength > (i - flag) ? maxLength:(i - flag);
            flag = tmp + 1;
        }
    }
    maxLength =maxLength>(i - flag)? maxLength:(i - flag);
    return maxLength;
}

int lengthOfLongestSubstring(char* s) {
    // 解法2：通过leetcode
    int i = 0,i_start_substring = 0,max = 0,h_index;;
    int n = 128;
    int *h_arr = (int *) malloc (n*sizeof(int)) ;
    memset(h_arr, -1, n*sizeof(h_arr[0]));
    while(*(s+i)!=NULL)
    {
        h_index = *(s+i);
        if(h_arr[h_index] >= i_start_substring)
        {
            i_start_substring = h_arr[h_index]+1;
        }
        h_arr[h_index] = i;
        max = (max < (i-i_start_substring+1))?i-i_start_substring+1:max;
        i++;
    }
    free(h_arr);
    return max;
}