Optimized Python Solution for Lexicographically Smallest String – Beats 100% in Time and Space
\n\n\n# Intuition\nThe problem asks for the lexicographically smallest string after performing a substring operation. The operation involves decrementing charac
\n![Screenshot from 2024-10-21 12-08-51.png](https://assets.leetcode.com/users/images/9fb89255-50e1-4dba-ab6b-1fedee6b105e_1729505503.9106112.png)\n\n# Intuition\nThe problem asks for the lexicographically smallest string after performing a substring operation. The operation involves decrementing characters starting from the first non-\'a\' character. The approach is to reduce the value of the characters to achieve the smallest lexicographical order while taking care not to modify unnecessary parts of the string.\n\nThe key insight is:\n- Skip leading \'a\'s as modifying them will only make the string larger.\n- Decrement non-\'a\' characters until we hit another \'a\' or reach the end of the string.\n- Handle edge cases where all characters are \'a\'.\n\n# Approach\n1. **Skip Leading \'a\'s**: We scan the string and count all leading \'a\' characters since they shouldn\'t be altered.\n2. **Decrement Non-\'a\' Characters**: Starting from the first non-\'a\' character, we decrement each character (moving them towards \'a\'). We stop as soon as we encounter the next \'a\' or reach the end of the string.\n3. **Handle Edge Case**: If all characters are \'a\', the smallest lexicographical string can only be achieved by changing the last \'a\' to \'z\'.\n4. **Concatenation**: The solution constructs the final result using string slicing and concatenation without extra space.\n\n# Complexity\n- Time complexity: \n  The time complexity is $$O(n)$$ where $$n$$ is the length of the string. We iterate over the string at most twice.\n\n- Space complexity:\n  The space complexity is $$O(1)$$ since we aren\'t using any additional data structures that grow proportionally to the input size.\n\n# Code\n```python\nclass Solution:\n    def smallestString(self, s: str) -> str:\n        n = len(s)\n        count = 0\n        \n        # Count the leading \'a\'s\n        while count < n and s[count] == \'a\':\n            count += 1\n        \n        # If all characters are \'a\', change the last one to \'z\'\n        if count == n:\n            return s[:-1] + \'z\'\n        \n        # Find the first non-\'a\' and start decrementing\n        result = s[:count]  # Keep leading \'a\'s as is\n        i = count\n        \n        # Decrement characters from the first non-\'a\' until an \'a\' is found or the string ends\n        while i < n and s[i] != \'a\':\n            result += chr(ord(s[i]) - 1)\n            i += 1\n        \n        # Append the remainder of the string from where we stopped\n        result += s[i:]\n        \n        return result\n
['Python', 'Python3']