https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
主要思路：
网上的实现思路基本上都是基于滑动窗口：
- 通过1个hashmap来保存当前字符上次出现的index
- 遍历字符串，若当前字符s[pos]上次在位置i出现，则当前长度= pos - i，否则为之前累计长度+1。
但是好像都没提到动态规划，说白了其实这是1个动态规划的思路。状态转移方程dp[i]的含义：以当前字符s[i]结尾的的最常无重复字符子串，则状态转移方程为：
1. s[j] = s[j - 1] + 1, s[j]未出现过
2. s[j] = j - i, s[j]之前在位置i出现过
class Solution {
public:
int lengthOfLongestSubstring(std::string& s) {
if (s.length() <= 1) {
return s.length();
}
std::unordered_map<char, size_t> latest_index;
latest_index[s[0]] = 0;
int latest_len = 1;
int max_len = 1;
for (size_t pos = 1; pos < s.length(); ++pos) {
char current_char = s[pos];
if (latest_index.find(current_char) == latest_index.end() || latest_index[current_char] < pos - latest_len) {
latest_len = latest_len + 1;
} else {
latest_len = pos - latest_index[current_char];
}
latest_index[current_char] = pos;
max_len = latest_len > max_len ? latest_len : max_len;
}
return max_len;
}
};
