medium
1 views

Python Program To Find Sub-strings at least K vowels

Find and print all unique substrings containing at least K vowels in sorted order

Understand the Problem

Problem Statement

Given a string S of length L and an integer K, find all unique substrings that contain at least K vowels. The program must count and print these substrings in sorted order.

The substrings are formed by taking combinations of characters from the original string, and only unique combinations (regardless of order) are considered.

Constraints

  • 1 ≤ Length of string S ≤ 25
  • 1 ≤ K ≤ Length of string S
  • String S contains only lowercase and uppercase alphabets
  • Substrings are considered unique based on character combination, not position

Examples

Example 1
Input
apple
2
Output
8
ae
ale
ape
aple
appe
apple
Explanation

For the string 'apple' with K=2, we need substrings containing at least 2 vowels. The valid substrings are: ae, ale, ape, aple, appe, apple. These are all unique combinations of characters from 'apple' that contain at least 2 vowels (a and e).

Example 2
Input
management
4
Output
64
aaee
aaeen
aaeent
aaeet
aaeme
aaemen
aaement
aaemet
aagee
aageen
aageent
aageet
aageme
aagemen
aagement
aagemet
anaee
anaeen
anaeent
anaeet
anaeme
anaemen
anaement
anaemet
anagee
anageen
anageent
anageet
anageme
anagemen
anagement
anagemet
maaee
maaeen
maaeent
maaeet
maaeme
maaemen
maaement
maaemet
maagee
maageen
maageent
maageet
maageme
maagemen
maagement
maagemet
manaee
manaeen
manaeent
manaeet
manaeme
manaemen
manaement
manaemet
managee
manageen
manageent
manageet
manageme
managemen
management
managemet
Explanation

For the string 'management' with K=4, we need substrings containing at least 4 vowels. The string has vowels: a, a, e, e, a, e, e. We generate all combinations of these characters that result in substrings with 4 or more vowels, then sort them alphabetically.

Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_LEN 26
#define MAX_COMBOS 10000

// Function to check if character is vowel
bool isVowel(char c) {
    c = tolower(c);
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

// Function to count vowels in a string
int countVowels(char *str) {
    int count = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        if (isVowel(str[i])) {
            count++;
        }
    }
    return count;
}

// Function to check if substring already exists in array
bool existsInArray(char **arr, int size, char *str) {
    for (int i = 0; i < size; i++) {
        if (strcmp(arr[i], str) == 0) {
            return true;
        }
    }
    return false;
}

// Function to generate combinations
void generateCombinations(char *str, int len, int k, char **result, int *count, int start, char *current, int index) {
    if (index == k) {
        current[k] = '\0';
        if (countVowels(current) >= k) {
            if (!existsInArray(result, *count, current)) {
                result[*count] = (char*)malloc((k + 1) * sizeof(char));
                strcpy(result[*count], current);
                (*count)++;
            }
        }
        return;
    }
    
    for (int i = start; i < len; i++) {
        current[index] = str[i];
        generateCombinations(str, len, k, result, count, i + 1, current, index + 1);
    }
}

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

int main() {
    char str[MAX_LEN];
    int k;
    
    fgets(str, sizeof(str), stdin);
    str[strcspn(str, "\n")] = 0; // Remove newline
    scanf("%d", &k);
    
    int len = strlen(str);
    char *result[MAX_COMBOS];
    int count = 0;
    char current[MAX_LEN];
    
    // Generate combinations for all lengths from 1 to len
    for (int l = 1; l <= len; l++) {
        generateCombinations(str, len, k, result, &count, 0, current, 0);
    }
    
    // Sort the results
    qsort(result, count, sizeof(char*), compare);
    
    // Print results
    printf("%d\n", count);
    for (int i = 0; i < count; i++) {
        printf("%s\n", result[i]);
        free(result[i]);
    }
    
    return 0;
}
Time:O(2^n) where n is the length of string
Space:O(2^n) for storing all possible combinations
Approach:

C Solution Explanation:

  1. Input Handling: Read string and integer K using fgets and scanf, removing any trailing newline character
  2. Helper Functions:
    • isVowel(): Checks if a character is a vowel (case-insensitive)
    • countVowels(): Counts vowels in a given string
    • existsInArray(): Checks if a substring already exists in our results array
  3. Combination Generation: Uses recursive backtracking to generate all possible combinations of characters from the original string
  4. Validation: For each generated combination, checks if it contains at least K vowels and is unique
  5. Sorting: Uses qsort with strcmp for lexicographic sorting
  6. Memory Management: Dynamically allocates memory for results and properly frees it

Time Complexity: O(2^n) where n is string length (worst case for generating all combinations)

Space Complexity: O(2^n) for storing combinations

Visual Explanation

Loading diagram...
All Problems