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

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. 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 * 104
• s consists of lowercase English letters.
• letter is a lowercase English letter, and appears in s at least repetition times.

 

Solutions

Solution: Stack

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @param {character} letter
 * @param {number} repetition
 * @return {string}
 */
const smallestSubsequence = function (s, k, letter, repetition) {
  const n = s.length;
  const stack = [];
  let letterCount = 0;
  let required = repetition;

  for (const char of s) {
    if (char === letter) {
      letterCount += 1;
    }
  }

  for (let index = 0; index < n; index++) {
    const char = s[index];

    while (
      stack.length &&
      stack.at(-1) > char &&
      stack.length + n - index - 1 >= k &&
      (stack.at(-1) !== letter || letterCount > required)
    ) {
      const removeChar = stack.pop();

      if (removeChar === letter) {
        required += 1;
      }
    }

    if (char === letter) {
      letterCount -= 1;
    }

    if (stack.length >= k) continue;

    if (char === letter) {
      required -= 1;
      stack.push(char);
    } else if (k > stack.length + required) {
      stack.push(char);
    }
  }

  return stack.join('');
};