What is the brute force approach and complexity for Minimum Insertion Steps to Make a String Palindrome?

Ends match: solve the inside. Ends differ: insert one end, solve the rest, keep the cheaper choice with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Minimum Insertion Steps to Make a String Palindrome?

Compute the longest palindromic subsequence with one row, and return n minus it with optimal time complexity O(N^2) and space complexity O(N).

Minimum Insertion Steps to Make a String Palindrome

Q: How do you identify the pattern for Minimum Insertion Steps to Make a String Palindrome?

Look for key signals in the prompt: "minimum insertions" indicates Minimize the number of added letters. The answer is a cost, not a length.; "make the string a palindrome" indicates The final string is a palindrome, and the original letters that are not inserted must form one too.; "insert any character at any index" indicates An inserted letter can match any letter, so only the letters that stay in place matter..

Hard·LeetCode #1312 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given a string s. In one step you may insert any letter at any position in s, including the start and the end. Return the fewest insertions that turn s into a palindrome. A palindrome reads the same forwards and backwards.

Input

A string s of lowercase letters.

Output

The smallest number of insertions that makes s a palindrome.

Example 1

Input: s = "zzazz"

Output: 0

The string is already a palindrome, so nothing needs to be inserted.

Example 2

Input: s = "mbadm"

Output: 2

One result is mbdadbm. It inserts a d after the b and a b before the last m.

Example 3

Input: s = "leetcode"

Output: 5

One result is leetcodocteel, which adds five letters to the original eight.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimum insertions”

→ Minimize the number of added letters. The answer is a cost, not a length.

“make the string a palindrome”

→ The final string is a palindrome, and the original letters that are not inserted must form one too.

“insert any character at any index”

→ An inserted letter can match any letter, so only the letters that stay in place matter.

Approach Complexity Ladder

Brute Force — recursion on the rangeO(2^N)O(N)

Ends match: solve the inside. Ends differ: insert one end, solve the rest, keep the cheaper choice

Better — table dp[i][j] for every rangeO(N^2)O(N^2)

dp[i][j] is the fewest insertions for s[i..j]; fill the table from the last row up

Optimal — one row of LPS, then n − LPSO(N^2)O(N)

Compute the longest palindromic subsequence with one row, and return n minus it

Brute Force Intuition

For s[i..j]: if s[i] = s[j], the ends pair up for free, so the cost is the cost of the inside. If they differ, one insertion settles one end. Insert a copy of s[i] on the right, which leaves s[i+1..j]. Or insert a copy of s[j] on the left, which leaves s[i..j−1]. Take the cheaper of the two, plus 1.

Recognition rule for this sub-pattern:

dp[i][j] for the substring s[i..j]; expand from the centre or fill by increasing length.

Remember this · DP — Strings

Trigger

Longest common subsequence, edit distance, palindromes, matching with wildcards, interleaving.

Think

Look at the last characters: if they match, what do I do? If not, what are my options?

Key question

What does dp[i][j] mean, and what are the empty-string base cases?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture