Break a Palindrome - Practice Coding Problems

Break a Palindrome - Problem

String Greedy Medium

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

Input & Output

Example 1 — Replace First Non-'a'

$ Input: palindrome = "abccba"

› Output: "aaccba"

💡 Note: The first non-'a' character is 'b' at position 1. Replace it with 'a' to get "aaccba", which is not a palindrome and lexicographically smallest.

Example 2 — All Characters Are 'a'

$ Input: palindrome = "aa"

› Output: "ab"

💡 Note: All characters are 'a', so we change the last character to 'b' to get "ab", which breaks the palindrome.

Example 3 — Single Character

$ Input: palindrome = "a"

› Output: ""

💡 Note: Cannot break a single character palindrome while maintaining the same length, so return empty string.

Constraints

1 ≤ palindrome.length ≤ 1000
palindrome consists of only lowercase English letters
palindrome is a palindrome

Visualization

Tap to expand

Understanding the Visualization

Input

Palindromic string like "racecar"

Process

Find first non-'a' character and replace with 'a'

Output

Lexicographically smallest non-palindrome "aacecar"

Key Takeaway

🎯 Key Insight: To get the lexicographically smallest result, replace the first non-'a' character with 'a', or if all are 'a', change the last to 'b'

Asked in

F Facebook 15 a Amazon 12 G Google 8 M Microsoft 6

The key insight is to make the lexicographically smallest change by replacing the first non-'a' character with 'a'. If all characters are 'a', change the last one to 'b'. Best approach is greedy with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Positions	O(n²)	O(n)	Try replacing each character with every possible letter and find the lexicographically smallest non-palindrome
Greedy - Replace First Non-'a' with 'a'	O(n)	O(n)	Find the first character that isn't 'a' and replace it with 'a' for lexicographically smallest result

Brute Force - Try All Positions — Algorithm Steps

Step 1: For each position i in the string
Step 2: For each letter 'a' to 'z', replace character at position i
Step 3: Check if result is not a palindrome
Step 4: Keep track of lexicographically smallest valid result

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Position 0

Replace 'a' with 'b', 'c', 'd'... and check palindrome

Try Position 1

Replace 'b' with 'a', 'c', 'd'... and check palindrome

Find Minimum

Among all valid results, return lexicographically smallest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isPalindrome(const char* s) {
    int len = strlen(s);
    int left = 0, right = len - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

char* solution(char* palindrome) {
    int len = strlen(palindrome);
    if (len == 1) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    char* best = NULL;
    
    for (int i = 0; i < len; i++) {
        for (char c = 'a'; c <= 'z'; c++) {
            if (c != palindrome[i]) {
                char* candidate = malloc(len + 1);
                strcpy(candidate, palindrome);
                candidate[i] = c;
                
                if (!isPalindrome(candidate)) {
                    if (best == NULL || strcmp(candidate, best) < 0) {
                        free(best);
                        best = candidate;
                    } else {
                        free(candidate);
                    }
                } else {
                    free(candidate);
                }
            }
        }
    }
    
    if (best == NULL) {
        best = malloc(1);
        best[0] = '\0';
    }
    
    return best;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n positions, we try 26 characters and check palindrome in O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Creating new strings for each attempt

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 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 Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler