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


# Submitted by Samy Vilar <samy_vilar> on 07/18/2024

# Apply a nearest neighbor approach, while keeping track of the
# "ideal" solution thus far w/i a stack, we note for each successive
# symbol we can pop all those from the aforementioned solution while
# said current symbol is lesser and the eviction of said member
# would still lead to a pheassible solution; 
# intuitively for this to be the case the following 2 criteria have 
# to be met;

# - There are enough instances of our target letter w/i our heap and
#   and succeeding the current entry (inclussively) to generate at the
#   very least the given repitations;
#   Since the frequency of letter w/i our heap only changes when ever
#   we push/pop an instance of said letter, it would suffice to apply 
#   the aforementioned check when ever we are trying to "evict" an
#   instance of letter, essentially should there be r remaining instances
#   and we currently need m then we would need to halt should r < m + 1
#   otherwise we increment m and continue with the eviction;

# - There are enough symbols overall remaining w/i our heap and the
#   the current suffix of s; i.e. if we still an additional length 
#   symbols but s only has t remaining (inclussively) then intuitively
#   should t <= length, we couldn't possibly remove the current or
#   any further symbol as such we can safely yield the union of the
#   the two;

# @@ NOTE some care must be taken since our tentative solution may 
# exceed length, if we choose to take the first length symbols
# then we must take care it contains at the very least the k instances
# of letter, if not, we update each preceeding symbol until
# the aforementioned "missing" (if any) intances have being added;

# Since we are iterating through s twice, given we first have to 
# determine the overall number of letter instances and any symbol
# is pushed/popped at most twice would imply O(|s|) time/additional-space;


# version 1.1 based on other submission(s)
#             - instead of keeping track of the remaining and taken letter counts;
#               the same can be achieved by keeping track of "excess" instances
#               i.e. if there are m overall instances and of those we must take
#               k, then at best we could disregard/pop m - k excess instance(s);
#               as such we decrement said excess counter while it remains positive 
#               when ever we evict an instance of letter from our stack, otherwise
#               break;
#             - the same approach can be applied over the other counter, i.e.
#               we can halt and return as soon as |s| - length evictions have
#               being made;

class Solution:
    def smallestSubsequence(self, s: str, length: int, letter: str, k: int) -> str:        
        append = (pending := deque()).append
        excess = s.count(letter) - k
        residual = len(s) - length + 1
        for at, ch in enumerate(s):
            while pending and ch < pending[-1]:                
                if pending[-1] == letter:
                    if not excess:
                        break
                    excess -= 1                    
                if not (residual := residual - 1):                    
                    return ''.join(pending) + s[at:]                    
                del pending[-1]                
            append(ch)            
        pending = list(islice(pending, length))
        if 0 < (k := k - pending.count(letter)):
            for at in count(length - 1, -1):
                if pending[at] != letter:
                    pending[at] = letter
                    if not (k := k - 1):
                        break                                
        return ''.join(pending)      

            
            
        
291