Minimum insertions to make string palindrome
Goldman Sachs
OracleThe 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)
{
}
}go
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
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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question