3. Longest Substring Without Rep

写了一下午的所谓动态规划，结果在最复杂的输入面前TLE。看了只有9行的C++ SOLUTION，拿出来分析一下。

int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}

核心：一个字母碰见两次，肯定是重复子串了。
如果已经记录的，上一次出现的位置，比现有的起始位置更加大，说明这个字母先重复了，包含两个重复字母的字串都不算数了，将这个字母和之前的串CUT掉，从这个字母的下一个字母起重新计算长度，再次出现，再次重新记录，以此类推。
遍历字符串：
第一次碰见字符，只记录，第二次以上，将前面带有该字符的子串CUT掉重新记录开始位置。

学到的：
1、如果问题元素集合不太大，完全可以铺开来，不用担心浪费空间（典型的如ASCII字母表）
2、别上来就往算法书教的那几种算法上靠，分析问题本身，看有什么特征，再确定思路，往算法书上的算法靠是下下策，那些都是通用解法。