Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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.
Example 1:
Input: s = "zzazz" Output: 0 Explanation: The string "zzazz" is already palindrome we do not need any insertions.
Example 2:
Input: s = "mbadm" Output: 2 Explanation: String can be "mbdadbm" or "mdbabdm".
Example 3:
Input: s = "leetcode" Output: 5 Explanation: Inserting 5 characters the string becomes "leetcodocteel".
Constraints:
1 <= s.length <= 500s consists of lowercase English letters.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
"zzazz"
"mbadm"
"leetcode"
minimum-number-of-moves-to-make-palindrome)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1312: Minimum Insertion Steps to Make a String Palindrome
class Solution {
private Integer[][] f;
private String s;
public int minInsertions(String s) {
this.s = s;
int n = s.length();
f = new Integer[n][n];
return dfs(0, n - 1);
}
private int dfs(int i, int j) {
if (i >= j) {
return 0;
}
if (f[i][j] != null) {
return f[i][j];
}
int ans = 1 << 30;
if (s.charAt(i) == s.charAt(j)) {
ans = dfs(i + 1, j - 1);
} else {
ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
}
return f[i][j] = ans;
}
}
// Accepted solution for LeetCode #1312: Minimum Insertion Steps to Make a String Palindrome
func minInsertions(s string) int {
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= j {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := 1 << 30
if s[i] == s[j] {
ans = dfs(i+1, j-1)
} else {
ans = min(dfs(i+1, j), dfs(i, j-1)) + 1
}
f[i][j] = ans
return ans
}
return dfs(0, n-1)
}
# Accepted solution for LeetCode #1312: Minimum Insertion Steps to Make a String Palindrome
class Solution:
def minInsertions(self, s: str) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= j:
return 0
if s[i] == s[j]:
return dfs(i + 1, j - 1)
return 1 + min(dfs(i + 1, j), dfs(i, j - 1))
return dfs(0, len(s) - 1)
// Accepted solution for LeetCode #1312: Minimum Insertion Steps to Make a String Palindrome
struct Solution;
use std::collections::HashMap;
impl Solution {
fn min_insertions(s: String) -> i32 {
let n = s.len();
let s: Vec<char> = s.chars().collect();
let mut memo: HashMap<(usize, usize), i32> = HashMap::new();
Self::dp(0, n, &mut memo, &s)
}
fn dp(start: usize, end: usize, memo: &mut HashMap<(usize, usize), i32>, s: &[char]) -> i32 {
let n = end - start;
if n < 2 {
return 0;
}
if let Some(&res) = memo.get(&(start, end)) {
return res;
}
let res = if s[start] == s[end - 1] {
Self::dp(start + 1, end - 1, memo, s)
} else {
1 + Self::dp(start, end - 1, memo, s).min(Self::dp(start + 1, end, memo, s))
};
memo.insert((start, end), res);
res
}
}
#[test]
fn test() {
let s = "zzazz".to_string();
let res = 0;
assert_eq!(Solution::min_insertions(s), res);
let s = "mbadm".to_string();
let res = 2;
assert_eq!(Solution::min_insertions(s), res);
let s = "leetcode".to_string();
let res = 5;
assert_eq!(Solution::min_insertions(s), res);
let s = "g".to_string();
let res = 0;
assert_eq!(Solution::min_insertions(s), res);
let s = "no".to_string();
let res = 1;
assert_eq!(Solution::min_insertions(s), res);
}
// Accepted solution for LeetCode #1312: Minimum Insertion Steps to Make a String Palindrome
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1312: Minimum Insertion Steps to Make a String Palindrome
// class Solution {
// private Integer[][] f;
// private String s;
//
// public int minInsertions(String s) {
// this.s = s;
// int n = s.length();
// f = new Integer[n][n];
// return dfs(0, n - 1);
// }
//
// private int dfs(int i, int j) {
// if (i >= j) {
// return 0;
// }
// if (f[i][j] != null) {
// return f[i][j];
// }
// int ans = 1 << 30;
// if (s.charAt(i) == s.charAt(j)) {
// ans = dfs(i + 1, j - 1);
// } else {
// ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
// }
// return f[i][j] = ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.