Is Lexicographically Smallest Palindrome easy or hard?

Lexicographically Smallest Palindrome is classified as an Easy problem on LeetCode with an acceptance rate above 80%. The main insight is recognizing that each mirrored pair can be resolved greedily using the smaller character.

Lexicographically Smallest Palindrome Python/Java solution

In Python or Java, convert the string to a mutable structure such as a character array, then iterate with two pointers from both ends. When characters differ, assign the smaller character to both positions. The logic remains identical across languages and runs in O(n) time.

How to solve Lexicographically Smallest Palindrome in O(n)?

Use two pointers starting at indices 0 and n-1. If the characters match, move both pointers inward. If they differ, replace both with the smaller of the two characters. Continue until the pointers meet in the middle, producing the lexicographically smallest palindrome in a single pass.

What is the best approach for Lexicographically Smallest Palindrome?

The best approach is a greedy two-pointer algorithm. Start with pointers at the beginning and end of the string and compare characters. If they differ, replace both with the smaller character. This guarantees the lexicographically smallest palindrome while running in O(n) time and O(1) space.

Is Lexicographically Smallest Palindrome asked at Google/Amazon/Meta?

Palindrome transformation and lexicographic minimization patterns appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the underlying two-pointer and greedy reasoning is commonly tested in string manipulation questions.

What data structure is used in Lexicographically Smallest Palindrome?

The solution primarily uses a string or character array and the two-pointer technique. No additional data structures are required for the optimal algorithm, which keeps the space complexity constant.

What is the time complexity of Lexicographically Smallest Palindrome?

The optimal solution runs in O(n) time because each pair of characters is processed once using two pointers moving toward the center. Space complexity is O(1) since the string can be modified in place without extra data structures.

Description Hints 2 Solution Video 6:31

2697. Lexicographically Smallest Palindrome

Easy81.1% acceptance3 companies

You are given a string s consisting of lowercase English letters, and you are allowed to perform operations on it. In one operation, you can replace a character in s with another lowercase English letter.

Your task is to make s a palindrome with the minimum number of operations possible. If there are multiple palindromes that can be made using the minimum number of operations, make the lexicographically smallest one.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Return the resulting palindrome string.

Example 1:

Input: s = "egcfe"
Output: "efcfe"
Explanation: The minimum number of operations to make "egcfe" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "efcfe", by changing 'g'.

Example 2:

Input: s = "abcd"
Output: "abba"
Explanation: The minimum number of operations to make "abcd" a palindrome is 2, and the lexicographically smallest palindrome string we can get by modifying two characters is "abba".

Example 3:

Input: s = "seven"
Output: "neven"
Explanation: The minimum number of operations to make "seven" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "neven".

Constraints:

1 <= s.length <= 1000
s consists of only lowercase English letters.

Asked at 3 companies

Mathworks PayPal Meta

Topics

Hints open one at a time

Hint 1

We can make any string a palindrome, by simply making any character at index i equal to the character at index length - i - 1 (using 0-based indexing).

Hint 2

To make it lexicographically smallest we can change the character with maximum ASCII value to the one with minimum ASCII value.

6:31

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def makeSmallestPalindrome(self, s: str) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"egcfe"

Input

"abcd"

Input

"seven"

Your code is saved on this device.Solution