剑指 Offer II 017. 含有所有字符的最短字符串

题目链接：剑指 Offer II 017. 含有所有字符的最短字符串

方法：同向双指针

解题思路

• 基本思路：统计 \(t\) 字符串中每个字符的个数，然后使用双指针遍历字符串 \(s\)，当窗口覆盖 \(t\) 中所有字符时，开始缩短左指针到可以到达的最右侧，取窗口最小的字符串为答案；
• 需要考虑的问题：
  • 什么情况下表明当前窗口覆盖了 \(t\) 中所有字符？
     由于 \(t\) 中的字符可能重复，可以设置一个变量 \(k\) 表示 \(t\) 中不重复的字符个数，在右指针右移的过程中当某个字符的个数减小为 \(0\) 时，表明当前窗口已经包含当前字符的所有重复字符，此时将 \(k - 1\) ，当 \(k == 0\) 时，表明已经完全覆盖。
  • 左指针可以右移的条件？
    • 若当前左指针指向的字符数量为负数，有两种可能：
      • 当前字符不在 \(t\) 字符串中，直接跳过即可，\(l + 1\)；
      • 当前字符在 \(t\) 字符串中，但是当前窗口中该字符的数量超过了 \(t\) 字符串中该字符的数量，也可以跳过，\(l + 1\)。
  • 答案何时更新？
     应该在左指针右移停止后。设答案字符串的起始为 \(idx\)，长度为 \(len\)，当 \(r - l > len\) 时，更新 \(idx = l\)，\(len = r - l\)。
• 注意：在此过程中 \(k\) 变量只在第一次使得窗口覆盖 \(t\) 字符串的过程中起作用，因为覆盖之后，右指针仍继续右移，并且左指针的移动，也确保了当前窗口在左指针右移之后仍然覆盖 \(t\) 字符串。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.length(), m = t.length();
        if (n < m) return "";
        int cnt['z' + 1] = {0}, k = 0;
        for (auto &c : t) {
            cnt[c] ++ ;
            if (cnt[c] == 1) k ++ ;
        }
        int l = 0, r = 0, idx = 0, len = n;
        while (r < n) {
            char c = s[r ++ ];
            cnt[c] -- ;
            if (cnt[c] == 0) k -- ;
            if (k == 0) {
                while (l < r && cnt[s[l]] < 0) {
                    cnt[s[l]] ++ ;
                    l ++ ;
                }
                if (l == r || r - l < len) {
                    idx = l;
                    len = r - l;
                }
            }
        }
        return k != 0 ? "" : s.substr(idx, len);
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。