LeetCode in Kotlin

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

Hard

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.

Solution

@Suppress("NAME_SHADOWING")
class Solution {
    fun smallestSubsequence(s: String, k: Int, letter: Char, repetition: Int): String {
        var repetition = repetition
        var count = 0
        for (c in s.toCharArray()) {
            count += if (c == letter) 1 else 0
        }
        val sb = StringBuilder()
        var i = 0
        while (i < s.length) {
            while (sb.length + s.length > i + k && sb.isNotEmpty() &&
                s[i] < sb[sb.length - 1] && (sb[sb.length - 1] != letter || count != repetition)
            ) {
                repetition += if (sb[sb.length - 1] == letter) 1 else 0
                sb.setLength(sb.length - 1)
            }
            if (k - sb.length > Math.max(0, if (s[i] == letter) 0 else repetition)) {
                sb.append(s[i])
                repetition -= if (s[i] == letter) 1 else 0
            }
            count -= if (s[i++] == letter) 1 else 0
        }
        return sb.toString()
    }
}

This site is open source. Improve this page.