题目：
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;
}
