How do you solve Lexicographically Smallest Palindrome on LeetCode?

Lexicographically Smallest Palindrome (LeetCode #2697) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Changing the larger character to the smaller one ensures the palindrome is lexicographically smallest.

What is the brute force solution for Lexicographically Smallest Palindrome?

The brute force approach for Lexicographically Smallest Palindrome is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all possible combinations of character replacements to form a palindrome. This method is straightforward but inefficient, as it doesn't leverage any specific properties of palindromes. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Lexicographically Smallest Palindrome?

Lexicographically Smallest Palindrome uses the following concepts: Two Pointers, String, Greedy. The recommended patterns to study are: Two Pointers, Greedy.

What are the interview tips for Lexicographically Smallest Palindrome?

Always explain your thought process clearly while coding. Consider edge cases and test your solution with them. Practice writing clean and efficient code, as readability matters in interviews.

What are common mistakes when solving Lexicographically Smallest Palindrome?

Not considering the lexicographical order when making replacements. Failing to handle edge cases, such as strings of length 1 or already being a palindrome.

#2697

Lexicographically Smallest Palindrome

Easy

Two PointersStringGreedyTwo PointersGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a two-pointer technique to efficiently convert the string into a palindrome while ensuring it is lexicographically smallest. This method minimizes operations by directly comparing characters from both ends of the string.

⚙️

Algorithm

4 steps

1Step 1: Initialize two pointers, one at the start and one at the end of the string.
2Step 2: While the left pointer is less than or equal to the right pointer, compare the characters at both pointers.
3Step 3: If they are different, replace the larger character with the smaller one to ensure the palindrome is lexicographically smallest.
4Step 4: Move the pointers towards the center and repeat until all characters are checked.

solution.py14 lines

1def make_palindrome(s):
2    s = list(s)
3    left, right = 0, len(s) - 1
4    while left <= right:
5        if s[left] != s[right]:
6            min_char = min(s[left], s[right])
7            s[left] = min_char
8            s[right] = min_char
9        left += 1
10        right -= 1
11    return ''.join(s)
12
13# Example usage:
14print(make_palindrome('egcfe'))

ℹ

Complexity note: The complexity is O(n) because we only traverse the string once with two pointers, making it efficient in terms of time. The space complexity is O(n) due to the conversion of the string into a character array.

1Changing the larger character to the smaller one ensures the palindrome is lexicographically smallest.
2Using two pointers allows for efficient comparison and modification of characters.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.