We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest K-Length Subsequence With Occurrences of a Letter

Difficulty: Hard

Problem Description

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. 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.

Key Insights

  • The problem requires constructing a subsequence of a specific length while ensuring a certain letter appears a minimum number of times.
  • A greedy approach can be employed, where we aim to build the result character by character, always considering the smallest lexicographical option.
  • A stack can be used to manage the characters of the resultant subsequence, allowing easy access to the last character added and enabling the removal of characters that would result in a smaller lexicographical order.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, since we traverse the string once. Space Complexity: O(k), where k is the length of the resulting subsequence, as we store the characters in a stack.

Solution

To solve the problem, we will use a stack to build the resulting subsequence. We iterate through the string s while maintaining a count of how many times the letter appears in the remaining part of the string. We ensure that the constructed subsequence meets the length requirement and contains the required occurrences of the specified letter.

  1. Initialize a stack to hold the characters of the resulting subsequence.
  2. Track the count of the specified letter and how many characters are still needed to complete the subsequence.
  3. Iterate through each character in the string s:
    • Use a loop to pop characters from the stack if the current character is smaller than the top of the stack and if popping does not prevent us from meeting the length and letter requirements.
    • Push the current character onto the stack.
    • Adjust counts for the specified letter as necessary.
  4. Finally, construct the result from the stack, ensuring it is of length k and contains the required number of occurrences of the specified letter.

Code Solutions

def smallestKLengthSubsequence(s: str, k: int, letter: str, repetition: int) -> str:
    stack = []
    letter_count = s.count(letter)
    to_pick = k
    
    for char in s:
        while stack and stack[-1] > char and len(stack) + (len(s) - s.index(char)) > to_pick and (stack[-1] != letter or letter_count > repetition):
            stack.pop()
        
        if len(stack) < to_pick:
            if char == letter:
                stack.append(char)
                if letter_count > repetition:
                    letter_count -= 1
            elif to_pick - len(stack) > repetition:
                stack.append(char)

    return ''.join(stack[:k])
← Back to All Questions