Martina DNA
The core thinking is Sliding Window Algorithm.
int findMinSubstringLength(const vector<int>& s, const unordered_map<int, int>& requiredCounts) {
unordered_map<int, int> windowCounts;
int minLength = INT_MAX;
int left = 0, right = 0;
int satisfied = 0;
while (right < s.size()) {
int rightInt = s[right];
if (requiredCounts.find(rightInt) != requiredCounts.end()) {
windowCounts[rightInt]++;
if (windowCounts[rightInt] == requiredCounts.at(rightInt)) {
satisfied++;
}
}
while (satisfied == requiredCounts.size()) {
minLength = min(minLength, right - left + 1);
int leftInt = s[left];
if (requiredCounts.find(leftInt) != requiredCounts.end()) {
windowCounts[leftInt]--;
if (windowCounts[leftInt] < requiredCounts.at(leftInt)) {
satisfied--;
}
}
left++;
}
right++;
}
return minLength == INT_MAX ? -1 : minLength;
}