<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:
        # Convert string to list since strings are immutable in Python
        s = list(s)
        n = len(s)
        
        # Initialize the starting index of the substring to be replaced
        start = 0
        
        # Flag to check if we have performed the operation at least once
        operation_performed = False
        
        # Loop through the string
        while start < n:
            # Find the starting index of a substring containing only 'a's
            if s[start] == 'a':
                start += 1
                continue
            
            # Mark the operation as performed
            operation_performed = True
            
            # Replace characters in the substring until we encounter 'a' again
            while start < n and s[start] != 'a':
                s[start] = chr(ord(s[start]) - 1)
                start += 1
            
            # If we've performed the operation, break the loop
            if operation_performed:
                break
        
        # If no operation was performed, convert the last character to 'z'
        if not operation_performed:
            s[-1] = 'z'
        
        # Convert the list back to a string and return
        return ''.join(s)

# Example usage:
solution = Solution()
print(solution.smallestString("cbabc"))  # Output: "baabc"
print(solution.smallestString("aa"))  # Output: "az"
print(solution.smallestString("acbbc"))  # Output: "abaab"
print(solution.smallestString("leetcode"))  # Output: "kddsbncd"
160