{x}
blog image

Smallest K-Length Subsequence With Occurrences of a Letter

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.

 

Example 1:

Input: s = "leet", k = 3, letter = "e", repetition = 1
Output: "eet"
Explanation: There are four subsequences of length 3 that have the letter 'e' appear at least 1 time:
- "lee" (from "leet")
- "let" (from "leet")
- "let" (from "leet")
- "eet" (from "leet")
The lexicographically smallest subsequence among them is "eet".

Example 2:

example-2 
Input: s = "leetcode", k = 4, letter = "e", repetition = 2
Output: "ecde"
Explanation: "ecde" is the lexicographically smallest subsequence of length 4 that has the letter "e" appear at least 2 times.

Example 3:

Input: s = "bb", k = 2, letter = "b", repetition = 2
Output: "bb"
Explanation: "bb" is the only subsequence of length 2 that has the letter "b" appear at least 2 times.

 

Constraints:

  • 1 <= repetition <= k <= s.length <= 5 * 104
  • s consists of lowercase English letters.
  • letter is a lowercase English letter, and appears in s at least repetition times.

Solution Explanation:

This problem asks to find the lexicographically smallest subsequence of length k from a given string s containing the letter letter at least repetition times. The solution employs a greedy approach using a monotonic stack.

Algorithm:

  1. Initialization: Create a stack stack to store the characters of the subsequence, and an integer letterCount to track the occurrences of letter in the subsequence.

  2. Iteration: Iterate through the string s. For each character c:

    • Case 1: c is not letter: If the stack has less than k - repetition characters, and c is smaller than the top of the stack (if the stack is not empty), pop the top element from the stack and push c. This ensures that we are always selecting smaller characters whenever possible to maintain lexicographical order. If the stack has k-repetition characters already or if c is not smaller than the top of the stack, we push c to the stack only if the number of elements in the stack is less than k.

    • Case 2: c is letter: Push c to the stack. Increment letterCount.

  3. Post-processing: If the stack has less than k elements, append the remaining characters from the input string that are lexicographically smaller than the top of the stack to get a subsequence of length k.

  4. Return: Convert the stack into a string and return it.

Time Complexity Analysis:

The algorithm iterates through the string s once, and the stack operations (push and pop) take constant time. The overall time complexity is O(N), where N is the length of the string s.

Space Complexity Analysis:

The space complexity is O(k) due to the stack which stores at most k characters.

Python3 Code:

def smallestSubsequence(s, k, letter, repetition):
    stack = []
    letterCount = 0
    for c in s:
        while stack and stack[-1] > c and len(stack) - (c == letter) + len(s) - s.index(c) -1 >= k - repetition and letterCount < repetition:
            if stack[-1] == letter:
                letterCount -= 1
            stack.pop()
        if len(stack) < k:
            if c == letter:
                letterCount += 1
            stack.append(c)
 
    return "".join(stack)

Java Code:

import java.util.Stack;
 
class Solution {
    public String smallestSubsequence(String s, int k, char letter, int repetition) {
        Stack<Character> stack = new Stack<>();
        int letterCount = 0;
        for (char c : s.toCharArray()) {
            while (!stack.isEmpty() && stack.peek() > c && stack.size() - (stack.peek() == letter ? 1 : 0) + s.length() - s.indexOf(c) - 1 >= k - repetition && letterCount < repetition) {
                if (stack.pop() == letter) {
                    letterCount--;
                }
            }
            if (stack.size() < k) {
                if (c == letter) {
                    letterCount++;
                }
                stack.push(c);
            }
        }
        return String.valueOf(stack.toArray()).replaceAll(", ", "");
 
    }
}

C++ Code:

#include <string>
#include <stack>
 
using namespace std;
 
string smallestSubsequence(string s, int k, char letter, int repetition) {
    stack<char> st;
    int letterCount = 0;
    for (char c : s) {
        while (!st.empty() && st.top() > c && st.size() - (st.top() == letter) + s.length() - s.find(c) - 1 >= k - repetition && letterCount < repetition) {
            if (st.top() == letter) letterCount--;
            st.pop();
        }
        if (st.size() < k) {
            if (c == letter) letterCount++;
            st.push(c);
        }
    }
    string res = "";
    while (!st.empty()) {
        res = st.top() + res;
        st.pop();
    }
    return res;
}

Go Code:

import (
	"bytes"
	"strings"
)
 
func smallestSubsequence(s string, k int, letter byte, repetition int) string {
	stack := []byte{}
	letterCount := 0
	for i := range s {
		c := s[i]
		for len(stack) > 0 && stack[len(stack)-1] > c && len(stack)-(byte(stack[len(stack)-1])==letter) + len(s)-i-1 >=k-repetition && letterCount < repetition {
			if stack[len(stack)-1] == letter {
				letterCount--
			}
			stack = stack[:len(stack)-1]
		}
		if len(stack) < k {
			if c == letter {
				letterCount++
			}
			stack = append(stack, c)
		}
	}
	return string(stack)
}

The provided codes implement the greedy algorithm described above. They differ slightly in syntax and handling of string manipulation but share the core logic. Remember to handle edge cases carefully in your implementation, especially scenarios where the stack becomes empty during the iteration.