Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: ""pwwkew""
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
思路：贪心法(C++)
假设子串里含有重复字符，则父串一定含有重复字符，单个子问题就可以决定父问题，因此可以用贪心法。跟动规不同，动规里，单个子问题只能影响父问题，不足以决定父问题。
从左往右扫描，当遇到重复字母时，以上一个重复字母的index+1，作为新的搜索起始位置，直到最后一个字母，复杂度是O(n)。如下图所示。
不含重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int ASCII_MAX = 255;
int last[ASCII_MAX]; // 记录字符上次出现过的位置
int start = 0; // 记录当前子串的起始位置
fill(last, last + ASCII_MAX, -1); // 0也是有效位置，因此初始化为-1
int max_len = 0;
for (int i = 0; i < s.size(); i++) {
if (last[s[i]] >= start) {
max_len = max(i - start, max_len);
start = last[s[i]] + 1;
}
last[s[i]] = i;
}
return max((int)s.size() - start, max_len); // 别忘了最后一次，例如"abcd"
}
};
时间复杂度o(n),空间复杂度o(1)