2030. Smallest K-Length Subsequence With Occurrences of a Letter

Oct 7, 2021

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:

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 * 10^4

• s consists of lowercase English letters.

• letter is a lowercase English letter, and appears in s at least repetition times.

Basic Idea:

相当于是需要找到一个长度为k的subsequence，其中需要包含至少repetition个“letter“，而且这个subsequence需要保证其是所有可能子串中字典序最小的。因为数据量很大，我们需要在O(N^2) 一下的时间内解决。

基本思路是把整个过程想象为一个栈，从左向右扫描s，在栈中尽量维持一个递增的序列。用两个变量记录一共可以删掉的字符个数以及可以删掉的“letter“ 字符的个数，如果遇到了栈顶比当前字符大的情况，如果仍然有可以删字符的quota，就将栈顶字符删掉，然后将当前字符放入。这样最终就可以得到字典续最小的子串。另外需要注意结束之后还要检查剩余的删除字符quota是否为0，如果不为0，则需要从后往前继续删除。

Java Code:

class Solution {
    public String smallestSubsequence(String s, int k, char letter, int repetition) {
        Deque<Character> stack = new ArrayDeque<>();
        int totalDeleteQuota = s.length() - k;
        int letterDeleteQuota = 0;
        for (char c : s.toCharArray()) {
            if (c == letter) {
                letterDeleteQuota++;
            }
        }
        letterDeleteQuota -= repetition;
        
        for (char c : s.toCharArray()) {
            if (stack.isEmpty() || stack.peekFirst() <= c) {
                stack.offerFirst(c);
            } else {
                while (!stack.isEmpty() && stack.peekFirst() > c
                      && (stack.peekFirst() != letter && totalDeleteQuota > 0 
                          || stack.peekFirst() == letter && letterDeleteQuota > 0 && totalDeleteQuota > 0)) {
                    char deleted = stack.pollFirst();
                    if (deleted == letter) {
                        letterDeleteQuota--;
                    }
                    totalDeleteQuota--;
                }
                stack.offerFirst(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            char c = stack.pollFirst();
            if (totalDeleteQuota == 0 || c == letter && letterDeleteQuota == 0) {
                sb.append(c);
            } else {
                totalDeleteQuota--;
                if (c == letter) letterDeleteQuota--;
            }
        }
        return sb.reverse().toString();
    }
}