Lexicographically Smallest Palindrome - Practice Coding Problems

Lexicographically Smallest Palindrome - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcd"

› Output: "abba"

💡 Note: Compare 'a' and 'd': choose 'a' for both positions. Compare 'b' and 'c': choose 'b' for both positions. Result is "abba" with 2 operations.

Example 2 — Already Palindrome

$ Input: s = "aa"

› Output: "aa"

💡 Note: String is already a palindrome, no operations needed.

Example 3 — Single Character

$ Input: s = "a"

› Output: "a"

💡 Note: Single character is always a palindrome, no operations needed.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Original string with potential mismatches

Process

Compare characters from both ends, fix with smaller character

Output

Resulting palindrome that is lexicographically smallest

Key Takeaway

🎯 Key Insight: Use two pointers and always choose the lexicographically smaller character when fixing mismatches

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use two pointers from both ends of the string. When characters don't match, choose the lexicographically smaller one for both positions. This ensures minimum operations while maintaining lexicographic order. Best approach is Two Pointers: Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Possibilities	O(26ⁿ)	O(26ⁿ)	Generate all possible palindromes and find the lexicographically smallest
Two Pointers - Compare from Ends	O(n)	O(n)	Use two pointers from start and end, fix mismatches with smaller character

Brute Force - Try All Possibilities — Algorithm Steps

Step 1: Generate all possible character replacements
Step 2: Check which combinations form palindromes
Step 3: Count operations for each palindrome
Step 4: Return lexicographically smallest with minimum operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Try all 26 characters at each position

Check

Verify if result forms a palindrome

Select

Choose lexicographically smallest with minimum operations

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <limits.h>

char best[1001];
int minOps;

void generatePalindromes(int pos, char* current, int operations, int n) {
    if (pos > n / 2) {
        // Complete palindrome
        for (int i = 0; i < n / 2; i++) {
            current[n - 1 - i] = current[i];
        }
        
        if (operations < minOps || (operations == minOps && strcmp(current, best) < 0)) {
            strcpy(best, current);
            minOps = operations;
        }
        return;
    }
    
    // Try all 26 characters
    for (char c = 'a'; c <= 'z'; c++) {
        char newCurrent[1001];
        strcpy(newCurrent, current);
        int newOps = operations;
        
        if (newCurrent[pos] != c) {
            newOps++;
        }
        newCurrent[pos] = c;
        
        if (pos != n - 1 - pos) {
            if (newCurrent[n - 1 - pos] != c) {
                newOps++;
            }
            newCurrent[n - 1 - pos] = c;
        }
        
        generatePalindromes(pos + 1, newCurrent, newOps, n);
    }
}

char* solution(char* s) {
    int n = strlen(s);
    strcpy(best, s);
    minOps = INT_MAX;
    
    generatePalindromes(0, s, 0, n);
    return best;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(26ⁿ)

Try 26 characters for each of n positions

✓ Linear Growth

Space Complexity

O(26ⁿ)

Store all possible string combinations

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Possibilities — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler