LeetCode HOT100 - 无重复字符的最长子串

无重复字符也就是一段区间中没有重复的字符（感觉在说废话）

但是从这个角度出发就是这个字符和它前一次出现的位置构成了可能可行的区间

因为它不可能到前一次出现的位置

于是我们预处理出这个东西

然后遍历，每次维护最前能到多少，因为比如 1221，对 下标 4 来说前一个是下标 1 ，对下标 3 来说前一个是下标 2 ，区间中都要满足所以我们对 “前一个” 取 max

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();unordered_map<char, vector<int>> mp;for (int i = 0; i < n; i++) {mp[s[i]].emplace_back(i);}vector<int> pre(n);for (auto [_, a] : mp) {int m = a.size();pre[a[0]] = -1;for (int i = 1; i < m; i++) {pre[a[i]] = a[i - 1];}}int ans = 0;int cur = -1;for (int i = 0; i < n; i++) {cur = max(cur, pre[i]);ans = max(i - cur, ans);}return ans;}
};