<p>You are given a string <code>s</code>, an integer <code>k</code>, a letter <code>letter</code>, and an integer <code>repetition</code>.</p>

<p>Return <em>the <strong>lexicographically smallest</strong> subsequence of</em> <code>s</code><em> of length</em> <code>k</code> <em>that has the letter</em> <code>letter</code> <em>appear <strong>at least</strong></em> <code>repetition</code> <em>times</em>. The test cases are generated so that the <code>letter</code> appears in <code>s</code> <strong>at least</strong> <code>repetition</code> times.</p>

<p>A <strong>subsequence</strong> is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.</p>

<p>A string <code>a</code> is <strong>lexicographically smaller</strong> than a string <code>b</code> if in the first position where <code>a</code> and <code>b</code> differ, string <code>a</code> has a letter that appears earlier in the alphabet than the corresponding letter in <code>b</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leet&quot;, k = 3, letter = &quot;e&quot;, repetition = 1
<strong>Output:</strong> &quot;eet&quot;
<strong>Explanation:</strong> There are four subsequences of length 3 that have the letter &#39;e&#39; appear at least 1 time:
- &quot;lee&quot; (from &quot;<strong><u>lee</u></strong>t&quot;)
- &quot;let&quot; (from &quot;<strong><u>le</u></strong>e<u><strong>t</strong></u>&quot;)
- &quot;let&quot; (from &quot;<u><strong>l</strong></u>e<u><strong>et</strong></u>&quot;)
- &quot;eet&quot; (from &quot;l<u><strong>eet</strong></u>&quot;)
The lexicographically smallest subsequence among them is &quot;eet&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="example-2" src="https://assets.leetcode.com/uploads/2021/09/13/smallest-k-length-subsequence.png" style="width: 339px; height: 67px;" />
<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;, k = 4, letter = &quot;e&quot;, repetition = 2
<strong>Output:</strong> &quot;ecde&quot;
<strong>Explanation:</strong> &quot;ecde&quot; is the lexicographically smallest subsequence of length 4 that has the letter &quot;e&quot; appear at least 2 times.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bb&quot;, k = 2, letter = &quot;b&quot;, repetition = 2
<strong>Output:</strong> &quot;bb&quot;
<strong>Explanation:</strong> &quot;bb&quot; is the only subsequence of length 2 that has the letter &quot;b&quot; appear at least 2 times.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= repetition &lt;= k &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
	<li><code>letter</code> is a lowercase English letter, and appears in <code>s</code> at least <code>repetition</code> times.</li>
</ul>

class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, rep: int) -> str:
        # lex smallest: minimize prefix at all costs
        # the rep copies of letter do NOT need to be contiguous


        # general concept:
        #   for each character:
        #      > while we can pop the top char from the stack to reduce the prefix with current letter: do it
        #      > if the prefix has room: add the character

        # N = len(s)

        # need = rep
        # rem = sum(c == letter for c in s)

        # subseq = []
        # for i, c in enumerate(s):
        #     # print(f"{i=}, {c=}: {subseq=}")
        #     while subseq and k-(len(subseq)-1) <= N-i and subseq[-1] > c:
        #         # can pop from subseq, have enough remaining chars overall, and popping would reduce the subseq lex.
                
        #         if subseq[-1] != letter:
        #             # non-letter chars are all equivalent
        #             # print(f"  popped {subseq[-1]}")
        #             subseq.pop()
        #         elif need < rem:
        #             # if the char is letter then we can only pop if we can still achieve rep copies
        #             # print(f"  popped {subseq[-1]}")
        #             subseq.pop()
        #             need += 1
        #         else:
        #             # print(f"  stopped popping: {subseq[-1]=}, {letter=}, {need=}, {rem=}")
        #             break # can't pop

        #     if c != letter:
        #         # non-letter: only append if there's room in the subseq AND for the need>0 letter copies
        #         # this prevents filling subseq up with lex. low chars then not having space for letters
        #         if k - len(subseq) - max(need, 0) > 0:
        #             subseq.append(c)
        #     else:
        #         # letter char: no need to worry about letter copies because appending this will help
        #         if len(subseq) < k:
        #             subseq.append(c)
        #             need -= 1
        #         rem -= 1

        # # print(f"final {subseq=}")
        # return ''.join(subseq)


        #### SIMPLER: track number of pops we can do
        N = len(s)
        pops = N-k # max times we can pop any char
        lpops = s.count(letter) - rep # max times we can pop letter

        subseq = []

        # strategy:
        #    1. iterate over string, while curr char is lower and we can pop, pop. Then append each character
        #    2. in the end we're left with a string with at least the right length (can't exceed pops)
        #       and at least the right number of letter copies (can't exceed lpops either)
        #    3. the final string may have more than k chars, some of which are copies of letter
        #
        #        .......l......l....lll.....l.........l......l....   # lex min string without exceeding pops
        #                         k
        #                             rep = 4
        #        .......l......l.ll    # after deletions
        #
        #         letters came in order so we can delete any number of elements from subseq as long as we keep the remaining order
        #         need to delete elements from the first k until we have rep copies, this is what will give us the lex. min sequence
        
        subseq = []
        for c in s:
            while subseq and pops and c < subseq[-1]:
                if subseq[-1] == letter:
                    if lpops:
                        lpops -= 1
                    else:
                        break # prevent inf. loop

                # regardless: pop the char
                subseq.pop()
                pops -= 1

            subseq.append(c)

        # look over the first k characters and track the number of non-letter chars we can take
        # keep going until
        #   > we hit k: take first k as is
        #   > we run out of takes: use the letters in 0:i in order (lex. min prefix)
        #     and effectively delete remaining chars so we get lexMinPrefix+remainingLetterCopiesNeeded

        takes = k - rep # number of non-letter chars we can take
        i = 0
        while takes and i < k:
            if subseq[i] != letter:
                takes -= 1
            i += 1

        return ''.join(subseq[:i]) + letter*(k-i) # where we took <= takes letters among first k, then fill rest with letter
324