Minimum Insertion Steps to Make a String Palindrome

Minimum Insertion Steps to Make a String Palindrome - Problem

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Input & Output

Example 1 — Basic Case

$ Input: s = "zzazz"

› Output: 2

💡 Note: Insert 'z' at index 2 and 'a' at index 6 to get "zzzazzz" which is palindromic. We can also insert 'a' at index 1 and 'a' at index 3 to get "zaaazz", but that's not optimal.

Example 2 — Already Palindrome

$ Input: s = "racecar"

› Output: 0

💡 Note: The string is already a palindrome, so no insertions are needed.

Example 3 — Single Character

$ Input: s = "a"

› Output: 0

💡 Note: Single character is always a palindrome.

Constraints

1 ≤ s.length ≤ 500
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string that needs to become palindromic

Find Strategy

Determine minimum characters needed to insert

Result

Return the minimum number of insertion steps

Key Takeaway

🎯 Key Insight: Minimum insertions = string length - longest palindromic subsequence length

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is that minimum insertions equals string length minus the longest palindromic subsequence. Best approach uses 2D Dynamic Programming to find LPS efficiently. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(26^n)	O(n)	Try all possible character insertions recursively
Longest Palindromic Subsequence	O(n²)	O(n²)	Convert to finding longest palindromic subsequence
Memoization (Top-Down DP)	O(n²)	O(n²)	Use recursion with memoization to avoid recomputing subproblems
2D Dynamic Programming	O(n²)	O(n²)	Build solution bottom-up using a 2D DP table

Brute Force — Algorithm Steps

Check if current string is palindrome
If not, try inserting each character at each position
Recursively solve for each insertion
Return minimum steps among all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Palindrome

Test if current string is already palindromic

Try Insertions

For each position, try inserting each of 26 letters

Recurse

Recursively solve for each new string created

Code -

solution.c — C

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

int isPalindrome(char* s) {
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

int minInsertions(char* s) {
    if (isPalindrome(s)) {
        return 0;
    }
    
    int len = strlen(s);
    int minSteps = INT_MAX;
    
    for (int i = 0; i <= len; i++) {
        for (char c = 'a'; c <= 'z'; c++) {
            char* newString = malloc(len + 2);
            strncpy(newString, s, i);
            newString[i] = c;
            strcpy(newString + i + 1, s + i);
            
            int steps = 1 + minInsertions(newString);
            if (steps < minSteps) {
                minSteps = steps;
            }
            free(newString);
        }
    }
    
    return minSteps;
}

int solution(char* s) {
    return minInsertions(s);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(26^n)

For each position we try 26 characters, leading to exponential branching

✓ Linear Growth

Space Complexity

O(n)

Recursion call stack depth up to n

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~25 min Avg. Time

2.8K 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 — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler