Optimized Solution for Lexicographically Smallest String – Beats 100%"
\n\n# Intuition\nThe problem requires us to find the lexicographically smallest string that can be obtained after applying a substring operation. The operation 
![Screenshot from 2024-10-21 11-56-53.png](https://assets.leetcode.com/users/images/52335190-eed5-4a49-a8d2-6d52a6cf1bb9_1729504876.7895887.png)\n\n# Intuition\nThe problem requires us to find the lexicographically smallest string that can be obtained after applying a substring operation. The operation allows changing a substring (either partially or fully) of the given string to its lexicographically smallest form.\n\nThe first thought is that decreasing characters as early as possible will result in a smaller lexicographical string. This suggests that modifying the first non-\'a\' character is the key to finding the solution. \n\nWe also need to account for the case where the entire string is composed of the letter \'a\'. In such a case, the only way to decrease the lexicographical order is by changing the last character from \'a\' to \'z\'.\n\n# Approach\n1. **Identify Leading \'a\'s:** We start by iterating through the string to count all the leading \'a\' characters. These leading \'a\'s should not be altered, as modifying them would result in a larger lexicographical string.\n   \n2. **Modify First Non-\'a\' Substring:** Once we encounter the first non-\'a\' character, we begin decrementing each character in the string (starting from that character). The goal here is to reduce the value of the characters, moving them towards the smallest possible lexicographical string.\n\n3. **Handle Edge Case:** If the entire string is composed of \'a\'s, the lexicographically smallest modification would be to change the last \'a\' to \'z\'.\n\n4. **Construct the Result:** After performing the modifications, we return the resulting string.\n\n# Complexity\n- Time complexity: \n  The time complexity is $$O(n)$$ where $$n$$ is the length of the string. This is because we iterate through the string at most twice: once to count leading \'a\'s and once to decrement characters after the first non-\'a\' character.\n\n- Space complexity: \n  The space complexity is $$O(n)$$ since we are converting the string into a list for in-place modifications and then converting it back to a string at the end.\n\n# Code\n```python\nclass Solution:\n    def smallestString(self, s: str) -> str:\n        n = len(s)\n        s = list(s)\n        count = 0\n        for i in range(n):\n            if s[i] == \'a\':\n                count += 1\n            else:\n                break\n        if count == n:\n            return "a" * (n - 1) + "z"\n        for i in range(count, n):\n            if s[i] == \'a\':\n                break\n            s[i] = chr(ord(s[i]) - 1)\n        return "".join(s)\n
['Python', 'Python3']