Minimum Insertions Palindrome
Python
Hard
3 views
Problem Description
A string s is provided (no spaces). Compute minimum insertions needed to make it a palindrome. Output the number.
Output Format
One integer.
Official Solution
import sys
s=sys.stdin.read().strip()
if not s: sys.exit(0)
# min insertions = n - LPS
n=len(s)
rev=s[::-1]
prev=[0]*(n+1)
for i in range(1,n+1):
cur=[0]*(n+1)
for j in range(1,n+1):
if s[i-1]==rev[j-1]:
cur[j]=prev[j-1]+1
else:
cur[j]=cur[j-1] if cur[j-1]>prev[j] else prev[j]
prev=cur
lps=prev[n]
sys.stdout.write(str(n-lps))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!