https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
給定一個(gè)字符串，找出不含有重復(fù)字符的最長子串的長度。

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 無重復(fù)字符的最長子串是 "abc"，其長度為 3。

示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 無重復(fù)字符的最長子串是 "b"，其長度為 1。

示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 無重復(fù)字符的最長子串是 "wke"，其長度為 3。
請(qǐng)注意，答案必須是一個(gè)子串，"pwke" 是一個(gè)子序列 而不是子串。

主要思路：

網(wǎng)上的實(shí)現(xiàn)思路基本上都是基于滑動(dòng)窗口：

1. 通過1個(gè)hashmap來保存當(dāng)前字符上次出現(xiàn)的index
2. 遍歷字符串，若當(dāng)前字符s[pos]上次在位置i出現(xiàn)，則當(dāng)前長度= pos - i，否則為之前累計(jì)長度+1。

但是好像都沒提到動(dòng)態(tài)規(guī)劃，說白了其實(shí)這是1個(gè)動(dòng)態(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;
    }
};