<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, repetition: int) -> str:
        rem_letter = 0
        for char in s:
            if char == letter:
                rem_letter += 1
        rem_length = len(s)
        used_letter = 0
        result = deque()
        for char in s:
            while True:
                can_remove_target = used_letter + rem_letter > repetition
                can_remove_any = len(result) + rem_length > k
                can_add_extra = len(result) + (repetition - used_letter) < k
                must_add = len(result) + rem_length <= k
                can_add_any = len(result) < k
                if must_add:
                    result.append(char)
                    break
                if len(result) == 0:
                    if char == letter:
                        result.append(char)
                        used_letter += 1
                        break
                    if can_add_extra:
                        result.append(char)
                        break
                    break
                if result[-1] != letter or can_remove_target:
                    if can_remove_any and char < result[-1]:
                        if result.pop() == letter:
                            used_letter -= 1
                        continue
                    #result.append(char)
                    #if char == letter:
                    #    used_letter += 1
                    #break
                if not can_add_extra and char != letter:
                    break
                if not can_add_any:
                    break
                result.append(char)
                if char == letter:
                    used_letter += 1
                break
            rem_length -= 1
            if char == letter:
                rem_letter -= 1
        #print(result)
        return "".join(result)

                
                


    def smallestSubsequence_bad(self, s: str, k: int, letter: str, repetition: int) -> str:
        rem_length = k
        rem_letter = repetition
        n = len(s)
        letters = "abcdefghijklmnopqrstuvwxyz"
        counts_before = [{char : 0 for char in letters} for i in range(0, n+1)]
        for i in range(0, n):
            for char in letters:
                counts_before[i+1][char] = counts_before[i][char]
            counts_before[i+1][s[i]] += 1
        search_start = 0
        search_end = 0
        result = ""
        while rem_length > 0:
            if rem_length == rem_letter:
                result = result + letter * rem_letter
                break
            while counts_before[n][letter] - counts_before[search_end+1][letter] >= rem_letter and n - search_end > rem_length:
                search_end += 1
            letter_to_use = None
            for char in letters:
                if counts_before[search_end+1][char] - counts_before[search_start][char]:
                    letter_to_use = char
                    break
            result = result + letter_to_use
            while s[search_start] != letter_to_use:
                search_start += 1
            search_start += 1
            if search_start > search_end:
                search_end = search_start
            rem_length -= 1
            if letter_to_use == letter:
                rem_letter -= 1
        return result
            
1078