https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
給定一個字符串，找出不含有重復(fù)字符的最長子串的長度哎垦。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 無重復(fù)字符的最長子串是 "abc"囱嫩，其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 無重復(fù)字符的最長子串是 "b"漏设，其長度為 1墨闲。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 無重復(fù)字符的最長子串是 "wke"，其長度為 3郑口。
請注意鸳碧，答案必須是一個子串，"pwke" 是一個子序列 而不是子串潘酗。
主要思路：
網(wǎng)上的實(shí)現(xiàn)思路基本上都是基于滑動窗口：
- 通過1個hashmap來保存當(dāng)前字符上次出現(xiàn)的index
- 遍歷字符串杆兵，若當(dāng)前字符s[pos]上次在位置i出現(xiàn)，則當(dāng)前長度= pos - i仔夺，否則為之前累計長度+1琐脏。
但是好像都沒提到動態(tài)規(guī)劃，說白了其實(shí)這是1個動態(tài)規(guī)劃的思路缸兔。狀態(tài)轉(zhuǎn)移方程dp[i]的含義：以當(dāng)前字符s[i]結(jié)尾的的最常無重復(fù)字符子串日裙，則狀態(tài)轉(zhuǎn)移方程為：
1. s[j] = s[j - 1] + 1, s[j]未出現(xiàn)過
2. s[j] = j - i, s[j]之前在位置i出現(xiàn)過
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;
}
};
