Question

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

Answer 1

#include <stdio.h>
#include <string.h>
#include <limits.h> // INT_MAX

#define MAX_CHAR 256

// Function to find the minimum substring
char* minSubstring(const char *s1, const char *s2, char *result) {
    int len1 = strlen(s1), len2 = strlen(s2);

    if (len1 == 0 || len2 == 0) return "";

    int charCount[MAX_CHAR] = {0};
    int substringCount[MAX_CHAR] = {0};

    // Build frequency table for s2
    int required = 0;
    for (int i = 0; i < len2; i++) {
        if (charCount[(unsigned char)s2[i]] == 0)
            required++;
        charCount[(unsigned char)s2[i]]++;
    }

    int left = 0, right = 0, formed = 0;
    int minLen = INT_MAX, start = 0;

    while (right < len1) {
        char ch = s1[right];
        substringCount[(unsigned char)ch]++;

        if (charCount[(unsigned char)ch] > 0 &&
            substringCount[(unsigned char)ch] == charCount[(unsigned char)ch]) {
            formed++;
        }

        while (left <= right && formed == required) {
            // Try to shrink the substring
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }

            char temp = s1[left];
            substringCount[(unsigned char)temp]--;

            if (charCount[(unsigned char)temp] > 0 &&
                substringCount[(unsigned char)temp] < charCount[(unsigned char)temp]) {
                formed--;
            }
            left++;
        }

        right++;
    }

    if (minLen == INT_MAX)
        return "";

    strncpy(result, s1 + start, minLen);
    result[minLen] = '\0';
}

int main() {
    const char *s1 = "ADOZBECYDEBAXC";
    const char *s2 = "ABC";
    char result[64] = "";

    minSubstring(s1, s2, result);
    if (strlen(result) > 0)
        printf("Minimum substring: %s\n", result);
    else
        printf("No valid substring found.\n");

    return 0;
}



/*
run:

Minimum substring: BAXC

*/

 

70+ SQL courses for beginners and professionals