正经题解｜ 追击123

题目大意

给你一个字符串 $s$ 长度为 $n$，字符串中只包含 $1$，$2$，$3$。

题意分析

找到一个最短的区间，区间内要同时出现，$1$，$2$，$3$。

解题思路

对于不能改变顺序的字符串，要想到如何遍历区间，减少遍历次数。

我们设区间为 $[L,R]$，始终保证区间是最短区间，我们可以用双指针来做。

• 初始化 $L = 0，R = 0$，一开始没有选择任何区间
• 拓展区间 $R+1$，记录当前区间内 $1$，$2$，$3$，出现的次数。
• 在区间满足的时候，不断缩减区间 $L+1$，同时更新$1$，$2$，$3$，出现的次数。

时间复杂度分析

区间中 $R$ 最多拓展到 $n$，$L$ 最多缩减到 $n$，复杂度为：$O(2 \times n)$。

代码演示

#include <bits/stdc++.h>
using namespace std;
int t;
bool check(unordered_map<char,int> &mp) {
    return mp['1'] > 0 && mp['2'] > 0 && mp['3'] > 0;
}
int main() {
    string s;
    cin >> t;
    while(t--) {
        unordered_map<char,int> mp;
        cin >> s;
        int l = 0,r = 0,len = s.length();
        int ans = 0;
        while(r < len) {
            mp[s[r]]++;
            if (check(mp) && ans == 0)ans = r - l + 1;
            while(check(mp) && l <= r) {
                ans = min(ans,r - l + 1);
                mp[s[l]]--;
                l++;
            }
            r++;
        }
        cout << ans << endl;
    }
    return 0;
}