<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:
        i = 0
        n = len(s)
        s = list(s)
        while i < n - 1 and s[i] == 'a':
            i += 1
        if i == n - 1:
            if s[i] == 'a':
                s[-1] = 'z'
            else:
                s[-1] = chr(ord(s[i]) - 1)
            return ''.join(s)
        while i < n and s[i] != 'a':
            s[i] = (chr(ord(s[i]) - 1))
            i += 1
        return ''.join(s)

#LOOK INTO BELOW -- how to do strings in DP
# class Solution:
#     def smallestString(self, s: str) -> str:
#         # Initialize a list to hold the string being built
#         new_s = [""] 

#         def helper(s, index, value, current_s):
#             if index == len(s):
#                 if new_s[0] == "" or current_s < new_s[0]:
#                     new_s[0] = current_s  # Update the reference
#                 return 0

#             c = s[index]
#             if c == 'a':
#                 prev_char = 'z'
#             else:
#                 prev_char = chr(ord(c) - 1)

#             # Recursive calls with updated strings
#             return min(
#                 helper(s, index + 1, value + ord(prev_char), current_s + prev_char),
#                 helper(s, index + 1, value + ord(c), current_s + c)
#             )

#         helper(s, 0, 0, "")
#         return new_s[0]

# class Solution:
#     def smallestString(self, s: str) -> str:
#         #skip any a's at the start.
#         #else, you need to judge if you turn it.
#         #can't predict. so DP? probably. 
#         new_s = [""] 
#         def helper(s, index, value, new_s):
#             print(new_s)
#             if index == len(s):
#                 return 0
#             c = s[index]
#             if c == 'a':
#                 prev_char = 'z'
#             else:
#                 prev_char = chr(ord(c) - 1)
#             return min(helper(s, index + 1, value + ord(prev_char), new_s + [prev_char]),
#             helper(s, index + 1, value + ord(c), new_s + [c]))
#         helper(s, 0, 0, new_s)
#         print(new_s)
#         return new_s[0]
                
           
        
        
157