2030. 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.

class Solution {
public:
    string smallestSubsequence(string s, int k, char letter, int repetition) {
        int letterCount = 0;
        for(auto ch : s)
            if(ch == letter)
                letterCount++;
        string res = "";
        
        for(int i = 0; i < s.length(); i++) {
            while(res.length() and k - res.length() < s.length() - i and res.back() > s[i]) {
                if(res.back() == letter) {
                    if(letterCount == repetition) break;
                    repetition++;
                }
                res.pop_back();
            }
            if(res.length() == k) {
                if(s[i] == letter) letterCount--;
                continue;
            }
            if(k - res.length() == repetition) {
                if(s[i] == letter) {
                    res += s[i];
                    repetition--;
                    letterCount--;
                }
            } else {
                res += s[i];
                if(s[i] == letter) {
                    repetition--;
                    letterCount--;
                }
            }
        }
        return res;
    }
};