<p>Given a string <code>s</code> consisting of lowercase English letters. Perform the following operation:</p>

<ul>
	<li>Select any non-empty <span data-keyword="substring-nonempty">substring</span> then replace every letter of the substring with the preceding letter of the English alphabet. For example, &#39;b&#39; is converted to &#39;a&#39;, and &#39;a&#39; is converted to &#39;z&#39;.</li>
</ul>

<p>Return the <span data-keyword="lexicographically-smaller-string"><strong>lexicographically smallest</strong></span> string <strong>after performing the operation</strong>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;cbabc&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;baabc&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>Perform the operation on the substring starting at index 0, and ending at index 1 inclusive.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;aa&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;az&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>Perform the operation on the last letter.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;acbbc&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;abaab&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>Perform the operation on the substring starting at index 1, and ending at index 4 inclusive.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;leetcode&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">&quot;kddsbncd&quot;</span></p>

<p><strong>Explanation:</strong></p>

<p>Perform the operation on the entire string.</p>
</div>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 3 * 10<sup>5</sup></code></li>
	<li><code>s</code> consists of lowercase English letters</li>
</ul>

class Solution:
    def smallestString(self, s: str) -> str:
        s_deque = collections.deque(s)
        res = []
        
        while len(s_deque) > 0 and s_deque[0] =="a":
            # start with a
            # "aaaa" or "abcda"...
            res.append("a")
            s_deque.popleft()
        
        done = False
        while len(s_deque)>0 and s_deque[0] != "a":
            done = True
            # "aabca": bc here
            # "aabac": b here
            res.append(chr(ord(s_deque[0])-1))
            s_deque.popleft()
        
        while len(s_deque)>0 and done:
            # "aabac": 2nd "a" here
            res.append(s_deque[0])
            s_deque.popleft()

        if done: 
            # "aabca" -> "aaaba"
            # "aabac" -> "aaaac"
            return "".join(res)

        return "".join(res[:-1:])+"z"

        


        

        



        # 0909-2024 self
        # if len(s) == 1:
        #     if s[0] == "a":
        #         return "z"
        #     else:
        #         return chr(ord(s[0])-1)
        # s_list = list(s)
        # if s_list[0] != "a":
        #     s_list[0] = chr(ord(s[0])-1)
        #     i = 1
        #     while i<len(s) and s_list[i]!= "a":
        #         s_list[i] = chr(ord(s[i])-1)
        #         i += 1
        # else:
        #     i = 1
        #     if s_list[i] == "a":
        #         while i<len(s_list) and s_list[i] == "a":
        #             if i == len(s_list)-1:
        #                 s_list[i] ="z"
        #             i+= 1
        #         while i<len(s) and s_list[i] != "a":
        #             s_list[i] = chr(ord(s[i])-1)
        #             i += 1
        #     elif s_list[i]!= "a":
        #         while i<len(s_list) and s_list[i]!= "a":
        #             s_list[i] = chr(ord(s[i])-1)
        #             i += 1
        # s= "".join(s_list)
        # return s

        
319