LeetCode 2697: Lexicographically Smallest Palindrome Solution

Master LeetCode problem 2697 (Lexicographically Smallest Palindrome), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2697. Lexicographically Smallest Palindrome

Easy

Two Pointers String Greedy

Problem Explanation

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.

Initialize two pointers left and right at the beginning and end of the string, respectively.
While left is less than or equal to right, compare characters at positions left and right.
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.
Decrement right after each comparison and increment left only when necessary.
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.

Solution Code

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);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2697 (Lexicographically Smallest Palindrome)?

This page provides optimized solutions for LeetCode problem 2697 (Lexicographically Smallest Palindrome) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2697 (Lexicographically Smallest Palindrome)?

The time complexity for LeetCode 2697 (Lexicographically Smallest Palindrome) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2697 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2697 in Java, C++, or Python.

Back to LeetCode Solutions