#2697

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Lexicographically Smallest Palindrome

Given a string, make it a palindrome with the fewest operations, prioritizing lexicographically smallest result.

Problem Statement

You are given a string s consisting of lowercase English letters. Your task is to make s a palindrome by performing the fewest possible operations. In each operation, you can replace a character in s with another lowercase English letter.

If there are multiple palindromes achievable with the same minimum number of operations, you must choose the lexicographically smallest palindrome. A string a is lexicographically smaller than string b if, at the first differing position, the character in a appears earlier in the alphabet than the corresponding character in b.

Examples

Example 1

Input: s = "egcfe"

Output: "efcfe"

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"

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"

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.

Solution Approach

Two-pointer approach

Use two pointers starting at both ends of the string. At each step, compare the characters at the two pointers. If they differ, replace the larger character with the smaller one to ensure the lexicographically smallest palindrome. This minimizes the number of operations by focusing on only the necessary modifications.

Greedy strategy

In addition to making the string a palindrome, prioritize making the lexicographically smallest choice by always picking the smaller character when characters mismatch. This greedy approach ensures that at every step, you are making the smallest possible change.

Optimized scanning

By scanning the string once from both ends, the solution operates in O(n) time complexity. This ensures that the solution is efficient, even for the maximum string length of 1000, while also keeping the space complexity low.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because each character in the string is visited once by the two-pointer approach. The space complexity is O(1) since no additional space is required beyond the input string.

What Interviewers Usually Probe

Tests understanding of two-pointer techniques and string manipulation.
Checks for the ability to implement a greedy strategy to minimize changes.
Evaluates efficiency in handling strings of up to 1000 characters.

Common Pitfalls or Variants

Common pitfalls

Over-complicating the approach by introducing unnecessary operations.
Failing to prioritize lexicographically smallest changes when characters mismatch.
Not optimizing the solution for time and space complexity, especially for larger input strings.

Follow-up variants

Consider an approach where the string is already a palindrome.
Test cases where multiple palindromes are possible with the same number of changes.
Explore the case where no changes are needed, testing the efficiency of the solution.

FAQ

How do I solve the Lexicographically Smallest Palindrome problem?

Use two-pointer scanning to compare characters at both ends of the string. Modify the larger character to the smaller one, ensuring minimal changes.

What is the time complexity of the Lexicographically Smallest Palindrome problem?

The time complexity is O(n), where n is the length of the string, as you only scan the string once with two pointers.

How do I prioritize the lexicographically smallest palindrome?

Whenever characters mismatch, replace the larger character with the smaller one to make the result lexicographically smallest.

What if the string is already a palindrome?

If the string is already a palindrome, no changes are needed, and the output will be the same as the input string.

Can I solve this problem without using the two-pointer technique?

While other techniques are possible, the two-pointer technique is the most efficient and optimal for this problem, ensuring minimal operations.

terminal

Solution

Solution 1: Greedy + Two Pointers

We use two pointers $i$ and $j$ to point to the beginning and end of the string, initially $i = 0$, $j = n - 1$.

1

2

3

4

5

6

7

8

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        cs = list(s)
        i, j = 0, len(s) - 1
        while i < j:
            cs[i] = cs[j] = min(cs[i], cs[j])
            i, j = i + 1, j - 1
        return "".join(cs)

Continue Practicing

#2486 append characters to string to make subsequence #2472 maximum number of non overlapping palindrome substrings #2938 separate black and white balls