<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:
        alpha = 'a b c d e f g h i j k l m n o p q r s t u v w x y z'.split(' ')
        ref = dict(zip(alpha, range(26)))
        # N = len(s)

        # netVal = 0
        # bestI = bestM = 0

        # for i in range(N):
        #     for m in range(i, N):
        #         c = s[m]
        #         net = abs(ref[c] - ((ref[c] - 1) % 26)) 
        #         if net > 0:
        #             bestI = i
        #             bestM = m
        # for i in range(bestI, bestM):
        #     s[i] = alpha[ref[s[i]] - 1]
        # return s

        r = 0
        s = list(s)
        changed = False
        while r < len(s):
            if s[r] != 'a':
                s[r] = alpha[(ref[s[r]] - 1) % 26]
                changed = True
            elif s[r] == 'a':
                if changed:
                    break
                r += 1
                continue
            r += 1 
        if r == len(s) and not changed:
            s[-1] = alpha[(ref[s[-1]] - 1) % 26]
        return ''.join(s)
184