Smallest K-Length Subsequence With Occurrences of a Letter

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

Understanding the Visualization

Input

String s, length k, target letter, minimum repetitions

Process

Use monotonic stack to build lexicographically smallest valid subsequence

Output

Subsequence of length k with required letter occurrences

Key Takeaway

🎯 Key Insight: Use a monotonic stack to greedily build the lexicographically smallest subsequence while tracking remaining target letters to ensure constraints can be met

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

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(2ⁿ × k)	O(k)	Generate all possible subsequences of length k and find the lexicographically smallest one with required letter count
Greedy with Monotonic Stack	O(n)	O(k)	Use a monotonic stack to build the lexicographically smallest subsequence while ensuring letter constraints

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler