题解 | #牛群名字覆盖# 双指针

知识点

双指针

思路

双指针，一个指针指向合法子字符串的开头，一个指向末尾，末尾不断向后移动，开头指向合法的最靠后的位置，如果符合要求则更新答案。

由于每个点只遍历一次，时间复杂度是线性的。

时间复杂度

AC code （C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return string字符串
     */
    string minWindow(string s, string t) {
        const int m = 52;
        vector<int> cnt(m, 0);
        for (auto c : t) {
            cnt[get(c)] += 1;
        }

        vector<int> now(m, 0);
        int n = s.size();
        string res = "";

        auto check = [&](int x) {
            now[x] -= 1;
            for (int i = 0; i < m; i ++) {
                if (now[i] < cnt[i]) {
                    now[x] += 1;
                    return false;
                }
            }
            now[x] += 1;
            return true;
        };

        for (int i = 0, j = 0; i < n; i ++) {
            now[get(s[i])] += 1;
            while (j <= i and check(get(s[j]))) {
                now[get(s[j ++])] --;
            }
            bool ok = true;
            for (int k = 0; k < m; k ++) {
                if (cnt[k] > now[k]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                if (res.empty() or res.size() > i - j + 1) res = s.substr(j, i - j + 1);
            }
        }
        return res;
    }
    int get(char c) {
        if (c >= 'A' and c <= 'Z') return c - 'A';
        return c - 'a' + 26;
    }
};