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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest K-Length Subsequence With Occurrences of a Letter

Number: 2157

Difficulty: Hard

Paid? No

Companies: Deutsche Bank

Problem Description

Given a string s, an integer k, a target letter, and an integer repetition, select a subsequence (i.e. preserve the order while dropping some characters) of s with exactly k characters so that the target letter appears at least repetition times. Among all possible subsequences satisfying the condition, return the lexicographically smallest one. It is guaranteed that s contains the target letter at least repetition times.

Key Insights

  • Use a greedy approach with a monotonic stack to build the smallest lexicographical result.
  • Maintain a count of how many target letters remain in s to decide safely whether to pop an element.
  • Only push a non-target letter if there is enough room left to still pick the required number of target letters.
  • While iterating, try to remove characters from the stack if the current character is smaller and there is enough room (both in terms of length and mandatory letter count) to improve the lexicographical order.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s (each character is processed at most once). Space Complexity: O(k), as we only keep a subsequence of length k in the stack.

Solution

The solution uses a greedy algorithm combined with a monotonic stack. As we iterate through the string, we attempt to maintain the smallest lexicographical order of the subsequence being built. At each character, we check if we can improve our current subsequence by removing an element from the end of the stack. However, we must ensure that by removing an element (especially if it is the target letter) we do not lose the ability to meet the required number of target letters later. To do this, we keep track of:

  • The number of elements currently in the subsequence (stack).
  • The number of target letters used.
  • The number of target letters remaining in the upcoming part of the string.

When deciding whether to push a non-target letter, we verify that there is enough remaining space so that even if we need to fill in with the target letter later, the length constraint k can still be met. This careful management of counts and conditions ensures that the final subsequence is both valid and lexicographically minimal.

Code Solutions

# Python solution with detailed comments
def smallestSubsequence(s, k, letter, repetition):
    n = len(s)
    total_letter = s.count(letter)  # Count of target letters in s
    stack = []                     # Monotonic stack to build the subsequence
    used_letter = 0                # Count of target letters included in the stack
    remaining_letter = total_letter  # How many target letters are left in s

    for i, ch in enumerate(s):
        if ch == letter:
            remaining_letter -= 1  # Use up one occurrence of target letter for future calculation

        # While the stack can be improved lexicographically:
        while stack and len(stack) + (n - i) > k and stack[-1] > ch:
            # If the top element is the target letter, check if we can safely remove it
            if stack[-1] == letter:
                if used_letter + remaining_letter > repetition:
                    stack.pop()
                    used_letter -= 1
                else:
                    break
            else:
                stack.pop()

        # Decide whether to push the current character.
        if len(stack) < k:
            if ch == letter:
                stack.append(ch)
                used_letter += 1
            else:
                # Only push non-target letters if we can still accommodate required target letters later.
                if k - len(stack) > repetition - used_letter:
                    stack.append(ch)
    return ''.join(stack)


# Example test cases:
print(smallestSubsequence("leet", 3, "e", 1))      # Output: "eet"
print(smallestSubsequence("leetcode", 4, "e", 2))    # Output: "ecde"
print(smallestSubsequence("bb", 2, "b", 2))          # Output: "bb"
← Back to All Questions