{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiearczvjykxeesis5khj52icvdcvwrfi3ljebftbnamhrusnfwoti",
    "uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mpm3ten6rkh2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreifluehife5guwi7vulbbvofd4xe3ucsgiabznjtxvibfngl45kc34"
    },
    "mimeType": "image/webp",
    "size": 55630
  },
  "path": "/jaspreet_singh_86ae1740ac/minimum-insertions-to-make-string-palindrome-mif",
  "publishedAt": "2026-07-01T17:22:52.000Z",
  "site": "https://dev.to",
  "tags": [
    "algorithms",
    "coding",
    "computerscience",
    "leetcode",
    "leetcode.com"
  ],
  "textContent": "\nleetcode.com\n\n\n##  Intuition\n\nAt first glance, it seems like we need to decide **where to insert characters** to make the string a palindrome.\n\nInstead of thinking about what to insert, think about **what we can keep**.\n\nThe characters that are already part of the **Longest Palindromic Subsequence (LPS)** do not need any insertion.\n\nOnly the remaining characters need to be inserted.\n\nFor example,\n\n\n\n    String\n\n    abcda\n\n\nThe Longest Palindromic Subsequence is\n\n\n\n    aca\n\n\nLength = **3**\n\nCharacters not in LPS\n\n\n\n    b\n    d\n\n\nThese are the characters we need to insert.\n\nHence,\n\n\n\n    Minimum Insertions = Length of String - Length of LPS\n\n\nNow the problem becomes finding the **Longest Palindromic Subsequence (LPS)**.\n\nEven better,\n\nThe **Longest Palindromic Subsequence** is simply the **Longest Common Subsequence (LCS)** between the string and its reverse.\n\nExample\n\n\n\n    Original\n\n    abcda\n\n    Reverse\n\n    adcba\n\n\nLCS\n\n\n\n    aca\n\n\nLength = **3**\n\nAnswer\n\n\n\n    5 - 3 = 2\n\n\n##  Brute Force Approach\n\nTry every possible insertion recursively.\n\nAt every mismatch,\n\n  * Insert the left character on the right.\n  * Insert the right character on the left.\n\n\n\nTake the minimum of both possibilities.\n\nExample\n\n\n\n    abc\n\n    ↓\n\n    Insert 'a'\n\n    ↓\n\n    Insert 'b'\n\n    ↓\n\n    Insert 'c'\n\n\nSince every mismatch creates two recursive choices, the number of possibilities grows exponentially.\n\n###  Complexity\n\n  * **Time:** `O(2^N)`\n  * **Space:** `O(N)` (Recursion Stack)\n\n\n\n##  Optimal Approach (Dynamic Programming)\n\n###  Observation\n\n\n    Minimum Insertions\n\n    =\n\n    Length of String\n\n    -\n\n    Longest Palindromic Subsequence\n\n\nAnd,\n\n\n\n    Longest Palindromic Subsequence\n\n    =\n\n    Longest Common Subsequence\n\n    (String, Reverse(String))\n\n\n###  Algorithm\n\n  1. Reverse the string.\n  2. Find the **Longest Common Subsequence (LCS)** between the original string and the reversed string.\n  3. Return:\n\n\n\n\n    Length - LCS\n\n\n###  Example\n\n\n    String\n\n    mbadm\n\n    Reverse\n\n    mdabm\n\n\nLCS\n\n\n\n    mam\n\n\nLength\n\n\n\n    3\n\n\nAnswer\n\n\n\n    5 - 3 = 2\n\n\n###  Java Code\n\n\n    public int minInsertions(String s) {\n\n        String rev = new StringBuilder(s).reverse().toString();\n\n        int n = s.length();\n        int[][] dp = new int[n + 1][n + 1];\n\n        for (int i = 1; i <= n; i++) {\n\n            for (int j = 1; j <= n; j++) {\n\n                if (s.charAt(i - 1) == rev.charAt(j - 1)) {\n                    dp[i][j] = 1 + dp[i - 1][j - 1];\n                } else {\n                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n                }\n            }\n        }\n\n        return n - dp[n][n];\n    }\n\n\n###  Complexity\n\n  * **Time:** `O(N²)`\n  * **Space:** `O(N²)`\n\n\n\n> **Interview One-Liner:** Convert the problem into finding the **Longest Palindromic Subsequence** , which can be computed as the **Longest Common Subsequence between the string and its reverse**.",
  "title": "Minimum Insertions to Make String Palindrome"
}