Problem 1312

Abstract / Summary

Find the longest palindromic subsequence to determine the fewest insertions needed to make the string a palindrome.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1312.py

class Solution:
    def minInsertions(self, s: str) -> int:
        @cache
        def deeper(left, right):
            if left >= right:
                return 0

            if s[left] == s[right]:
                return deeper(left+1, right-1)

            insertleft  = deeper(left+1, right)
            insertright = deeper(left, right-1)
            return 1 + min(insertleft, insertright)

        return deeper(0, len(s) - 1)
15 lines | 447 bytes | submitted September 17, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 74% (400k+ submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the classic problem of determining the minimum number of insertions required to transform a given string into a palindrome. It does so by employing a depth-first recursive strategy that explores the relationship between characters at symmetric positions and leverages memoization to avoid redundant computation. The algorithm is encapsulated in a single public method minInsertions, which delegates the heavy lifting to an inner helper function deeper.

Core Logic

At the heart of the solution lies a recursive function that examines a substring defined by two indices, left and right. The function returns the minimal insertion count needed to make the substring s[left:right+1] a palindrome. The base case triggers when the left index meets or surpasses the right index, indicating that the substring is either empty or a single character-both of which are inherently palindromic, requiring zero insertions.

if left >= right:
    return 0

When the characters at the current boundaries match, the algorithm proceeds inward without incurring any insertion cost, because the matching pair already satisfies the palindrome condition.

if s[left] == s[right]:
    return deeper(left + 1, right - 1)

If the characters differ, the algorithm considers two possibilities: inserting a character to match the left side or inserting a character to match the right side. Each option incurs a cost of one insertion plus the optimal cost of the resulting subproblem. The minimum of these two alternatives yields the optimal solution for the current substring.

insertleft  = deeper(left + 1, right)
insertright = deeper(left, right - 1)
return 1 + min(insertleft, insertright)

The public method initiates the recursion on the full string by calling deeper(0, len(s) - 1).

Recursive Structure

The recursion explores the problem space by progressively narrowing the interval [left, right]. Each recursive call reduces the interval length by at least one, guaranteeing eventual termination. The two recursive branches that arise when characters mismatch correspond to the two logical ways to resolve the mismatch: either treat the left character as if it were inserted on the right side, or treat the right character as if it were inserted on the left side. This exhaustive exploration ensures that the algorithm accounts for all possible insertion sequences, ultimately selecting the one with the smallest count.

Memoization

A critical performance feature is the use of the @cache decorator from Python’s functools module. By decorating deeper, the implementation automatically stores the result of each unique (left, right) pair. Subsequent calls with the same arguments retrieve the precomputed value instead of recomputing the subproblem. This transformation converts the naive exponential recursion into a dynamic programming solution with polynomial behavior, as each distinct sub-interval is evaluated at most once.

@cache
def deeper(left, right):
    ...

The memoization mechanism is transparent to the rest of the code, requiring no explicit dictionary management, and it integrates seamlessly with the recursive definition.

Edge Cases Handled

The algorithm gracefully handles several edge conditions without additional code:

  • An empty string results in left = 0 and right = -1. The base case left >= right evaluates to true, returning zero insertions, which is correct because an empty string is already a palindrome.
  • A single-character string yields left = 0 and right = 0. The base case again triggers, confirming that no insertions are needed.
  • Strings that are already palindromes cause the equality branch to fire at every level, leading to a cascade of recursive calls that simply shrink the interval until the base case, ultimately returning zero.
  • Strings with repeated characters but not fully palindromic still benefit from the equality check, reducing the number of recursive branches explored.

Performance Optimizations

Beyond memoization, the code exhibits a concise control flow that minimizes overhead. The early return when characters match prevents unnecessary branching, effectively pruning large portions of the recursion tree for inputs with many matching pairs. By directly returning the result of the inner recursive call in this scenario, the implementation avoids the extra work of evaluating the two insertion alternatives.

The use of Python’s built-in min function to select the cheaper insertion path is both readable and efficient, leveraging the interpreter’s optimized handling of primitive operations. Additionally, the function signatures and variable names are deliberately short, reducing attribute lookup costs during deep recursion.

Overall, the combination of a well-structured recursive decomposition, strategic early exits, and automatic caching yields a solution that scales efficiently with input size while maintaining clear and maintainable code.

written by openai gpt

ELI5 - Simplified Explanation

Imagine this code is playing a game to make a word a palindrome, which is a word that reads the same forwards and backwards, like radar. The code looks at the very first letter and the very last letter of the word at the same time. If those two letters match, it is happy, so it moves inward to look at the next pair of letters inside.

If the letters do not match, the code has to do a little bit of work to fix it. It thinks about adding a matching letter to one side or the other to make things balance out. It tries both ways to see which one takes the fewest steps to finish the puzzle.

There is a helpful trick called caching where the code remembers what it already figured out. If it sees the same pair of letters again, it does not need to do the thinking all over again because it already has the answer written down in a notebook. It keeps doing this until the whole word matches perfectly, and it counts how many letters it had to add along the way.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.07 | σ = 1.74

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Go Python
Progiez C++ Java Python
github begeekmyfriend C
black-shadows C++
charles-wangkai Java
everthis JS
fsq C++
JoshCrozier JS
lzl124631x C++
suxrobGM C#
varunu28 Java
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
Progiez C++, Java, Python
begeekmyfriend C
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fsq C++
JoshCrozier JavaScript
lzl124631x C++
suxrobGM C#
varunu28 Java
wisdompeak C++
24 links | 14 authors | 8 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

6 solutions   September 17, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality