Python Program To Sort K length Sub-Strings

Sort and print all unique combinations of substrings of length K from a given string

Understand the Problem

Problem Statement

Given a string S of length L and an integer K, the program must sort and print all the unique combinations of the substrings which are of length K.

Constraints

1 ≤ Length of string (L) ≤ 25
1 ≤ K ≤ L
String contains only lowercase letters
Output must be sorted lexicographically
Only unique combinations should be printed (no duplicates)

Examples

Example 1

Input

lemon
4

Output

emon
lemn
lemo
leon
lmon

Explanation

From 'lemon', we need all unique combinations of 4 characters. The possible combinations are: emon, lemn, lemo, leon, lmon. These are sorted lexicographically and printed.

Example 2

Input

apple
3

Output

ale
ape
apl
app
ple
ppe
ppl

Explanation

From 'apple', we need all unique combinations of 3 characters. The possible combinations are: ale, ape, apl, app, ple, ppe, ppl. These are sorted lexicographically and printed.

Solution

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

#define MAX_LEN 26
#define MAX_COMB 10000

// Structure to store a combination
typedef struct {
    char str[MAX_LEN];
} Combination;

// Global array to store combinations
Combination combinations[MAX_COMB];
int comboCount = 0;

// Function to check if a combination already exists
bool exists(char *str) {
    for (int i = 0; i < comboCount; i++) {
        if (strcmp(combinations[i].str, str) == 0) {
            return true;
        }
    }
    return false;
}

// Function to swap characters
void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

// Function to generate all permutations of a string
void permute(char *a, int l, int r, int k) {
    if (l == r) {
        a[k] = '\0'; // Null terminate at length k
        if (!exists(a)) {
            strcpy(combinations[comboCount].str, a);
            comboCount++;
        }
        return;
    }
    
    for (int i = l; i <= r; i++) {
        swap((a+l), (a+i));
        permute(a, l+1, r, k);
        swap((a+l), (a+i)); // backtrack
    }
}

// Function to generate all combinations using recursion
void generateCombinations(char *str, int start, char *current, int index, int k) {
    if (index == k) {
        current[k] = '\0';
        if (!exists(current)) {
            strcpy(combinations[comboCount].str, current);
            comboCount++;
        }
        return;
    }
    
    int len = strlen(str);
    for (int i = start; i < len; i++) {
        current[index] = str[i];
        generateCombinations(str, i + 1, current, index + 1, k);
    }
}

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

int main() {
    char str[MAX_LEN];
    int k;
    
    // Read input
    fgets(str, sizeof(str), stdin);
    str[strcspn(str, "\n")] = 0; // Remove newline
    
    scanf("%d", &k);
    
    char current[MAX_LEN];
    
    // Generate all combinations
    generateCombinations(str, 0, current, 0, k);
    
    // Sort combinations lexicographically
    qsort(combinations, comboCount, sizeof(Combination), compare);
    
    // Print results
    for (int i = 0; i < comboCount; i++) {
        printf("%s\n", combinations[i].str);
    }
    
    return 0;
}

Time:O(C(n,k) * k + C(n,k) * log(C(n,k))) where C(n,k) is the number of combinations

Space:O(C(n,k) * k) for storing all combinations

Approach:

C Solution Explanation:

Structure Definition: Define a Combination struct to store each result string
Global Variables: Use global array and counter to track all combinations
Existence Check: Function to check if a combination already exists (avoid duplicates)
Recursive Generation: Use backtracking to generate all combinations of length k
Sorting: Use qsort with strcmp for lexicographic ordering
Memory Management: Fixed-size arrays since constraints are small (L ≤ 25)

The algorithm generates all possible combinations by recursively selecting characters, ensuring uniqueness and proper sorting before output.

Visual Explanation

Loading diagram...

All Problems