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

# Problem:
#   - Given string 's'
#   - For any substring in 's', convert ea letter to prev letter in alphabet
#   - Return lexicographically smallest string after conversion

# Example:
#   s = 'cbabc'
#   substr = 'cb'
#   converted_substr = '[ba]abc'
#       - 

# Intuition:
#   1. Converting 'a' to 'z' becomes lexicographically larger
#   2. Converting any other letter makes the string lexicographically smaller
#   3. The lexicographically smallest converted substring requires:
#       - Finding the largest window (substr) to transform


# Cases:
#   1. Base case: single char
#   2. Two char: 
#       - 'ab' -> ['zb', 'aa', 'za]
#       - 'ba' -> ['aa', 'az', ']

class Solution:
    def smallestString(self, s: str) -> str:
        letters = 'abcdefghijklmnopqrstuvwxyz'

        # Base case: single char
        if len(s) == 1:
            idx = ord(s) - ord('a') - 1
            return letters[idx]
    
        # Sliding window
        #   s = 'aaac'
        #       l = 2 
        #       r = 3
        l = 0 # 2
        r = 0 # 2
        n = len(s)

        # Move both pointers to first non 'a' char
        while l + 1 < n and s[l] == 'a':
            l += 1
            r += 1
        
        # Move right pointer to last non 'a' char
        while r + 1 < n and s[r + 1] != 'a':
            r += 1
        
        # Convert characters in the substring
        converted = []

        for i in range(n):
            if l <= i <= r:
                prev_letter_idx = ord(s[i]) - ord('a') - 1
                prev_letter = letters[prev_letter_idx]
                converted.append(prev_letter)
            else:
                converted.append(s[i])

        return ''.join(converted)
316