Smallest K-Length Subsequence With Occurrences of a Letter - Problem

You are given a string s, an integer k, a letter letter, and an integer repetition.

Return the lexicographically smallest subsequence of s of length k that has the letter letter appear at least repetition times. The test cases are generated so that the letter appears in s at least repetition times.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input & Output

Example 1 — Basic Case

$ Input: s = "leetcode", k = 4, letter = "e", repetition = 2

› Output: "eetc"

💡 Note: We need a subsequence of length 4 with at least 2 'e's. "eetc" is lexicographically smallest among valid options like "eetc", "eeto", "eeco", etc.

Example 2 — Minimum Repetition

$ Input: s = "leetcode", k = 4, letter = "e", repetition = 1

› Output: "ecod"

💡 Note: With only 1 'e' required, we can pick the lexicographically smallest: 'e' from position 1, then 'c', 'o', 'd'.

Example 3 — All Required Letters

$ Input: s = "aaab", k = 3, letter = "a", repetition = 3

› Output: "aaa"

💡 Note: We need exactly 3 'a's in our subsequence of length 3, so we take all three 'a's.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ k ≤ s.length
1 ≤ repetition ≤ k
letter is a lowercase English letter
s contains at least repetition occurrences of letter

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is to use a monotonic stack to maintain lexicographical order while ensuring we can still meet the minimum letter requirement. The optimal approach uses a greedy strategy with O(n) time complexity, processing each character once and maintaining constraints efficiently.

Common Approaches

✓ Brute Force - Generate All Subsequences

⏱️ Time: O(2ⁿ × k) Space: O(k)

Generate every possible subsequence of length k from the string, check if it contains at least 'repetition' occurrences of the target letter, then return the lexicographically smallest valid one.

Greedy with Monotonic Stack

⏱️ Time: O(n) Space: O(k)

Build the result greedily using a stack. For each character, remove larger characters from the stack if we can still meet our constraints, then add the current character if needed.

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all subsequences of length k
Filter those with at least 'repetition' target letters
Return lexicographically smallest

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all k-length subsequences

Filter

Keep only those with enough target letters

Sort

Return lexicographically smallest

Code -

solution.c — C

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

#define MAX_LEN 1000
char validSubsequences[1000][MAX_LEN];
int validCount = 0;

void generateCombinations(const char* s, int index, char* current, int currentLen, int remaining, char targetLetter, int repetition, int sLen) {
    if (remaining == 0) {
        int count = 0;
        for (int i = 0; i < currentLen; i++) {
            if (current[i] == targetLetter) count++;
        }
        if (count >= repetition) {
            strcpy(validSubsequences[validCount], current);
            validCount++;
        }
        return;
    }
    
    if (index >= sLen) return;
    
    // Include current character
    current[currentLen] = s[index];
    current[currentLen + 1] = '\0';
    generateCombinations(s, index + 1, current, currentLen + 1, remaining - 1, targetLetter, repetition, sLen);
    
    // Exclude current character
    current[currentLen] = '\0';
    generateCombinations(s, index + 1, current, currentLen, remaining, targetLetter, repetition, sLen);
}

int compareStrings(const void* a, const void* b) {
    return strcmp((const char*)a, (const char*)b);
}

char* solution(char* s, int k, char* letter, int repetition) {
    validCount = 0;
    char current[MAX_LEN] = "";
    char targetLetter = letter[0];
    int sLen = strlen(s);
    
    generateCombinations(s, 0, current, 0, k, targetLetter, repetition, sLen);
    
    if (validCount == 0) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    qsort(validSubsequences, validCount, sizeof(validSubsequences[0]), compareStrings);
    
    char* result = malloc(strlen(validSubsequences[0]) + 1);
    strcpy(result, validSubsequences[0]);
    return result;
}

int main() {
    char s[MAX_LEN], letter[2];
    int k, repetition;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    scanf("%d", &k);
    getchar();
    
    fgets(letter, sizeof(letter), stdin);
    letter[strcspn(letter, "\n")] = 0;
    
    scanf("%d", &repetition);
    
    char* result = solution(s, k, letter, repetition);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × k)

Generate 2^n subsequences, check each of length k

✓ Linear Growth

Space Complexity

O(k)

Store current subsequence of length k

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Smallest K-Length Subsequence With Occurrences of a Letter - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler