Question

How to find the minimum substring of string s1 that includes every character of string s2 in C++

Answer 1

#include <iostream>
#include <string>
#include <climits> // INT_MAX
#include <unordered_map>
 
std::string minSubstring(const std::string& s1, const std::string& s2) {
    if (s2.empty() || s1.empty()) return "";
 
    // Frequency map for characters in s2
    std::unordered_map<char, int> charCount;
    for (char ch : s2) charCount[ch]++;
 
    int required = charCount.size(); // Number of unique characters in s2
    int left = 0, right = 0, formed = 0;
    std::unordered_map<char, int> substringCount;
    int minLen = INT_MAX, start = 0;
 
    while (right < s1.size()) {
        char ch = s1[right];
        substringCount[ch]++;
 
        if (charCount.count(ch) && substringCount[ch] == charCount[ch]) {
            formed++;
        }
 
        while (left <= right && formed == required) {
            char temp = s1[left];
 
            // Update the minimum substring
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
 
            substringCount[temp]--;
            if (charCount.count(temp) && substringCount[temp] < charCount[temp]) {
                formed--;
            }
            left++;
        }
        right++;
    }
 
    return minLen == INT_MAX ? "" : s1.substr(start, minLen);
}
 
int main() {
    std::string s1 = "ADOZBECYDEBAXC";
    std::string s2 = "ABC";
 
    std::string result = minSubstring(s1, s2);
    if (!result.empty()) {
        std::cout << "Minimum substring: " << result << std::endl;
    } else {
        std::cout << "No valid substring found." << std::endl;
    }
}
 
 
 
/*
run:
 
Minimum substring: BAXC
 
*/

 

70+ SQL courses for beginners and professionals