LeetCodeProblems/76.cpp at main · arsendulaev/LeetCodeProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//
// Created by arsen on 04.11.2025.
//
#include <climits>
#include <vector>
#include <string>
class Solution {
   public:
    std::string minWindow(std::string s, std::string t) {
        if (s.empty() || t.empty() || s.length() < t.length()) {
            return "";
        }
        std::vector<int> map(128, 0);
        for (int i = 0; i < t.size(); ++i) {
            map[t[i]]++;
        }
        int left = 0;
        int right = 0;
        int count = t.length();
        int min = INT_MAX;
        int startIndex = 0;
        while (right < s.length()) {
            if (map[s[right++]]-- > 0) {
                count--;
            }
            while (count == 0) {
                if (right - left < min) {
                    startIndex = left;
                    min = right - left;
                }
                if (map[s[left++]]++ == 0) {
                    count++;
                }
            }
        }
        return min == INT_MAX ? "" : s.substr(startIndex, min);
    }
};

/*
 * class Solution {
 * public:
 *     std::string minWindow(std::string s, std::string t) {
 *         if (s.length() < t.length()) {
 *             return "";
 *         }
 *         if (t.empty()) {
 *             return"";
 *         }
 *         if (s == t) {
 *             return s;
 *         }
 *         std::unordered_map<char, int> mapT;
 *         for (char c : t) {
 *             mapT[c]++;
 *         }
 *         int left = 0;
 *         int have = 0;
 *         std::unordered_map<char, int> mapCurrent;
 *         int bestL = INT_MAX;
 *         int bestI = 0;
 *         for (int i = 0; i < s.length(); ++i) {
 *             mapCurrent[s[i]]++;
 *             if (mapT.count(s[i]) && mapCurrent[s[i]] == mapT[s[i]]) {
 *                 have++;
 *             }
 *             while (have == mapT.size()) {
 *                 if (bestL > i - left + 1) {
 *                     bestL = i - left + 1;
 *                     bestI = left;
 *                 }
 *                 if (mapT.count(s[left]) && mapCurrent[s[left]] - 1 < mapT[s[left]]) {
 *                     have--;
 *                 }
 *                 mapCurrent[s[left++]]--;
 *             }
 *         }
 *         if (bestL == INT_MAX) {
 *             return "";
 *         }
 *         return s.substr(bestI, bestL);
 *     }
 * };
 */