<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:
        # string is composed only of As
        if set(s) == { 'a' }:
            output = ['a'] * (len(s) - 1)
            return ''.join(output) + 'z'

        # return s
        
        # find the earliest possible substring that ends before an a
        
        # use this index to find the earliest a possible
        if 'a' in s:
            aIndex = s.index('a')

            if aIndex == 0:
                # find the last appearance of a
                # move everything afterwards backwards

                start = aIndex + 1
                firstNonA = -1
                for i in range(0, len(s)):
                    if s[i] != 'a':
                        start = i
                        break
                lastNonA = -1
                for j in range(start, len(s)):
                    if s[j] != 'a':
                        if firstNonA == -1:
                            firstNonA = j
                        lastNonA = j

                    else:
                        # we have set our firstNonA
                        # and our lastNonA
                        break

                # retain everything before our firstNonA
                # move everything between our first and last nonA backwards
                # retain everything after the lastNonA

                substr = s[firstNonA:lastNonA + 1]
                # iterate through this substring
                shiftedSubstring = []
                for char in substr:
                    shiftedSubstring.append(chr(ord(char) - 1))
                
                return s[:firstNonA] + ''.join(shiftedSubstring) + s[lastNonA + 1:]


            else:
                substr = s[:aIndex]
                # iterate through this substring
                shiftedSubstring = []
                for char in substr:
                    shiftedSubstring.append(chr(ord(char) - 1))
                
                return ''.join(shiftedSubstring) + s[aIndex:]
        else:

            # iterate through this substring
            # shift the entire string by 1
            shiftedSubstring = []
            for char in s:
                shiftedSubstring.append(chr(ord(char) - 1))
            
            return ''.join(shiftedSubstring) 
121