Lexicographically Smallest Palindrome solution and explanation
9 more videos on this problem
Lexicographically Smallest Palindrome | leetcode Weekly 346 | Leetcode EasyBinaryMagic · 6:31 · 3K views
Leetcode Weekly contest 346 - Easy - Lexicographically Smallest PalindromePrakhar Agrawal · 5:40 · 1K views
Lexicographically Smallest Palindrome - Leetcode 2697 - PythonAlgorithms Casts · 10:09 · 928 views
Lexicographically Smallest Palindrome | Leetcode 2697 | Approach + Code with explanation.Pirai's Academy · 8:28 · 886 views
Leetcode 2697 || Lexicographically Smallest Palindrome || Leetcode Weekly Medium || cppKomal Pal · 7:08 · 812 views
Lexicographically Smallest Palindrome - LeetCode 2697 - Python Solution Code Answer ExplanationAlgoSkills · 10:53 · 560 views
Leetcode 2697. Lexicographically Smallest PalindromeElite Code · 17:53 · 499 views
2697. Lexicographically Smallest Palindrome | Leetcode | Strings | FundamentalsCoding with Tamilarasan · 5:47 · 449 views
2697. Lexicographically Smallest Palindrome (Leetcode Easy)Programming Live with Larry · 3:20 · 310 views
6454. Lexicographically Smallest Palindrome | Leetcode Weekly Contest 346 | Solution Code.Optimization · 0:50 · 271 views
The problem
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 <= 1000sconsists of only lowercase English letters.
Approach overview
Problem Overview: You receive a lowercase string s. You can replace any character with another lowercase letter. The goal is to transform the string into a palindrome while making the final result lexicographically smallest. The number of operations does not matter as long as the resulting string is the smallest possible palindrome.
Approach 1: Dynamic Programming (O(n²) time, O(n²) space)
This approach models the problem as building the smallest palindrome for every substring. Define dp[i][j] as the lexicographically smallest palindrome that can be formed from substring s[i..j]. If the characters at both ends match, extend the inner palindrome dp[i+1][j-1]. If they differ, replace the larger character with the smaller one and continue building inward. The DP table is filled for increasing substring lengths, combining results from previously solved subproblems.
Dynamic programming guarantees correctness for all substrings and demonstrates how local decisions affect the global lexicographic order. However, storing intermediate palindromes makes it memory heavy and slower than necessary. This method is mainly educational because the problem structure actually allows a simpler greedy observation. Concepts here overlap with common string DP problems where substrings are evaluated independently.
Approach 2: Iterative Two-Pointer Greedy (O(n) time, O(1) space)
The optimal observation: for every mirrored pair (i, j), the lexicographically smallest palindrome always uses the smaller of the two characters. Start two pointers at the beginning and end of the string. If s[i] == s[j], keep them unchanged. If they differ, replace both with min(s[i], s[j]). Move the pointers inward and repeat until they meet.
This works because lexicographic order depends on the earliest differing position. By forcing the smaller character at each mirrored pair, you minimize the string as early as possible without breaking the palindrome property. No backtracking or substring comparisons are needed. The algorithm scans the string once and modifies characters in place, making it both fast and memory efficient. This pattern is common in two pointers problems and relies on a simple greedy choice at every step.
Recommended for interviews: The iterative two-pointer greedy solution is what interviewers expect. It shows you recognize that lexicographic minimization can be decided locally for each mirrored pair. Mentioning the DP formulation demonstrates deeper reasoning about substring construction, but implementing the O(n) greedy approach proves you can simplify the problem once the key insight appears.
Approach 1: Approach 1: Dynamic Programming
This approach involves using dynamic programming to store solutions of subproblems and build up the solution to the original problem. This is beneficial when the problem can be broken down into overlapping subproblems with optimal substructures.
def solve(n, dp):
if n == 0 or n == 1:
return n
if dp[n] != -1:
return dp[n]
dp[n] = solve(n - 1, dp) + solve(n - 2, dp)
return dp[n]
n = 10
dp = [-1] * (n + 1)
print(solve(n, dp))import java.util.HashMap;
public class Fibonacci {
static HashMap<Integer, Integer> dp = new HashMap<>();
public static int solve(int n) {
if (n == 0 || n == 1) return n;
if (dp.containsKey(n)) return dp.get(n);
dp.put(n, solve(n - 1) + solve(n - 2));
return dp.get(n);
}
public static void main(String[] args) {
int n = 10;
System.out.println(solve(n));
}
}#include <iostream>
#include <vector>
using namespace std;
int solve(int n, vector<int> &dp) {
if (n == 0 || n == 1) return n;
if (dp[n] != -1) return dp[n];
return dp[n] = solve(n - 1, dp) + solve(n - 2, dp);
}
int main() {
int n = 10;
vector<int> dp(n + 1, -1);
cout << solve(n, dp) << endl;
return 0;
}const dp = [];
function solve(n) {
if (n === 0 || n === 1) return n;
if (dp[n] !== undefined) return dp[n];
dp[n] = solve(n - 1) + solve(n - 2);
return dp[n];
}
const n = 10;
console.log(solve(n));#include <stdio.h>
#define MAX 1000
int dp[MAX];
int solve(int n) {
if (n == 0 || n == 1) return n;
if (dp[n] != -1) return dp[n];
return dp[n] = solve(n - 1) + solve(n - 2);
}
int main() {
for (int i = 0; i < MAX; i++) dp[i] = -1;
int n = 10;
printf("%d\n", solve(n));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static Dictionary<int, int> dp = new Dictionary<int, int>();
static int Solve(int n) {
if (n == 0 || n == 1) return n;
if (dp.ContainsKey(n)) return dp[n];
dp[n] = Solve(n - 1) + Solve(n - 2);
return dp[n];
}
static void Main() {
int n = 10;
Console.WriteLine(Solve(n));
}
}The Python solution utilizes a list to memoize Fibonacci numbers. The function solves the problem recursively while storing results for reuse.
Time Complexity: O(n), Space Complexity: O(n) for the memoization list.
Approach 2: Approach 2: Iterative Solution
This approach converts the recursive solution into an iterative one. By using two variables to store intermediate Fibonacci numbers, we can achieve O(1) space complexity while maintaining a time complexity of O(n).
def solve(n):
if n == 0:
return 0
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
n = 10
print(solve(n))public class Fibonacci {
public static int solve(int n) {
if (n == 0) return 0;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
public static void main(String[] args) {
int n = 10;
System.out.println(solve(n));
}
}#include <iostream>
using namespace std;
int solve(int n) {
if (n == 0) return 0;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
int main() {
int n = 10;
cout << solve(n) << endl;
return 0;
}function solve(n) {
if (n === 0) return 0;
let a = 0, b = 1;
for (let i = 2; i <= n; i++) {
const c = a + b;
a = b;
b = c;
}
return b;
}
const n = 10;
console.log(solve(n));#include <stdio.h>
int solve(int n) {
if (n == 0) return 0;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
int main() {
int n = 10;
printf("%d\n", solve(n));
return 0;
}using System;
class Program {
static int Solve(int n) {
if (n == 0) return 0;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
static void Main() {
int n = 10;
Console.WriteLine(Solve(n));
}
}The iterative Python solution is simple and employs only two variables to achieve a constant space complexity.
Time Complexity: O(n), Space Complexity: O(1).
Approach 3: 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.
Next, each time we greedily modify s[i] and s[j] to their smaller value to make them equal. Then we move i one step forward and j one step backward, and continue this process until i \ge j. At this point, we have obtained the smallest palindrome string.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
function makeSmallestPalindrome(s: string): string {
const cs = s.split('');
for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
cs[i] = cs[j] = s[i] < s[j] ? s[i] : s[j];
}
return cs.join('');
}func makeSmallestPalindrome(s string) string {
cs := []byte(s)
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
cs[i] = min(cs[i], cs[j])
cs[j] = cs[i]
}
return string(cs)
}impl Solution {
pub fn make_smallest_palindrome(s: String) -> String {
let mut cs: Vec<char> = s.chars().collect();
let n = cs.len();
for i in 0..n / 2 {
let j = n - 1 - i;
cs[i] = std::cmp::min(cs[i], cs[j]);
cs[j] = cs[i];
}
cs.into_iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n), Space Complexity: O(n) for the memoization list. |
| Approach 2: Iterative Solution | Time Complexity: O(n), Space Complexity: O(1). |
| Greedy + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n²) | When exploring substring-based palindrome construction or demonstrating DP reasoning |
| Iterative Two-Pointer Greedy | O(n) | O(1) | Best for interviews and production code due to linear scan and constant memory |
Frequently asked questions
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.