Coding

Minimum insertions to make string palindrome

Asked at

Goldman Sachs

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string s, find the minimum number of insertions needed to make it a palindrome. A palindrome is a sequence that reads the same backward as forward. You can insert characters at any position in the string.

Input: s = "abcaa"

Output: 2

Explanation: Insert 2 characters "c", and "b" to make "abcacba", which is a palindrome.

Input: s = "ba"

Output: 1

Explanation: Insert "a" at the beginning to make "aba", which is a palindrome.

Input: s = "madam"

1 <= s.length <= 1000,
s consists of only lowercase English letters

cpp

class Solution{   
public: int minInsertion(string s) {
   
  }
};

java

class Solution {
    public int minInsertion(String s) {
        
    }
}

python

class Solution:
    def minInsertion(self, s):

javascript

class Solution {
    minInsertion(s) {
        
    }
}

csharp

class Solution
{
    public int minInsertion(string s)
    {
        
    }
}

func minInsertion(s string) int {
	
}

Stuck? Show a way to structure it+

01Observe that characters outside a longest palindromic subsequence must be inserted.
02Compute LPS as LCS of s and reverse(s).
03Return n minus the LPS length.
04Use rolling rows if only the count is required.

Reference answer

Keep the longest palindromic subsequence (LPS) and insert matching partners for every character outside it, so the minimum insertions equal n - LPS(s). Compute LPS by finding the longest common subsequence of s and reverse(s): dp[i][j] is the LCS length of the first i and j characters, with the usual match and max-of-neighbors recurrence. This is O(n^2) time and O(n^2) space, reducible to O(n) space with two rows. A direct interval DP also works: dp[l][r] is minimum insertions for s[l..r]. Do not confuse subsequence with substring; contiguous palindromes are insufficient.

Then expect these follow-ups

How would interval DP derive the same answer directly?
Tests: alternative DP
How would you reconstruct one resulting palindrome?
Tests: reconstruction

Hiring now

Get the Goldman Sachs interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question