LeetCode 2697: Lexicographically Smallest Palindrome

Explanation

To solve this problem, we can iterate through the string from both ends and make the characters at the corresponding positions equal by choosing the lexicographically smallest character. If the characters are already equal, we move to the next pair. After making the string a palindrome, if there are still remaining operations left, we can use them to make the string lexicographically smallest.

1. Initialize two pointers left and right at the beginning and end of the string, respectively.
2. While left is less than or equal to right, compare characters at positions left and right.
3. If the characters are not equal, replace the character at position left with the lexicographically smaller character between the characters at positions left and right.
4. Decrement right after each comparison and increment left only when necessary.
5. After making the string a palindrome, if there are remaining operations, update the string to make it lexicographically smallest.

Time complexity: O(n), where n is the length of the input string s. Space complexity: O(n) for storing the modified string.

class Solution {
    public String makePalindrome(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = s.length() - 1;
        int ops = 0;

        while (left <= right) {
            if (chars[left] != chars[right]) {
                chars[left] = chars[right] < chars[left] ? chars[right] : chars[left];
                ops++;
            }
            left++;
            right--;
        }

        if (ops > 0) {
            left = 0;
            right = s.length() - 1;

            while (left <= right && ops > 0) {
                if (chars[left] != 'a') {
                    chars[left] = 'a';
                    ops--;
                }
                if (chars[right] != 'a') {
                    chars[right] = 'a';
                    ops--;
                }
                left++;
                right--;
            }
        }

        return new String(chars);
    }
}