{"id":998,"date":"2025-08-26T16:24:03","date_gmt":"2025-08-26T10:54:03","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=998"},"modified":"2025-08-26T16:24:04","modified_gmt":"2025-08-26T10:54:04","slug":"minimum-insertion-steps-to-make-a-string-palindrome","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/minimum-insertion-steps-to-make-a-string-palindrome\/","title":{"rendered":"Minimum Insertion Steps to Make a String Palindrome | Leetcode 1312"},"content":{"rendered":"\n

Given a string s<\/code>, return the minimum number of insertions<\/strong> needed to make s<\/code> a palindrome. You can insert characters at any positions.<\/p>\n\n\n\n

Key observation: the minimum insertions required equals
len(s) - LPS(s)<\/code>
where LPS(s)<\/code> is the length of the Longest Palindromic Subsequence<\/strong> in s<\/code>. Since LPS(s) = LCS(s, reverse(s))<\/code>, this problem reduces to computing the Longest Common Subsequence<\/strong> between s<\/code> and reverse(s)<\/code>.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Example 1<\/strong><\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>:  <\/span>s = "zzazz"<\/span><\/span>\nOutput<\/span>: <\/span>0<\/span><\/span>\nExplanation<\/span>: <\/span>Already a palindrome.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Example 2<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>:  <\/span>s = "mbadm"<\/span><\/span>\nOutput<\/span>: <\/span>2<\/span><\/span>\nExplanation<\/span>: <\/span>One optimal result is "mbdadbm" after 2 insertions.<\/span><\/span><\/code><\/pre><\/div>\n\n\n
\n\t\t\t
\n\t\t\t\t
Content:<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\u00a0[show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>
\n\t\t\t
\n\t\t\t\t