Minimum Insertions to Make a Palindrome - Nutanix Online Assessment MNNIT Allahabad

Problem Preview

"A lab stores short symbol sequences that are supposed to read the same forwards and backwards. A transmission glitch dropped some symbols, leaving the sequence incomplete. To repair it, you may insert symbols anywhere in the string. You can insert any characters as many times as needed. Determine the minimum number of insertions required to make the string a palindrome. A palindrome is a string that reads the same from left to right and right to left. --- ## Example 1 **Input** ``` s = "ab" ``` **Output** ``` 1 ``` **Explanation** One possible repair is inserting `'a'` at the end to form `"aba"`. Another possible repair is inserting `'b'` at the front to form `"bab"`. Both require only one insertion. --- ## Example 2 **Input** ``` s = "mbadm" ``` **Output** ``` 2 ``` **Explanation** The string can be transformed into `"mbdadbm"` by inserting two characters. Therefore, the minimum number of insertions required is `2`. --- ## Input Format The input contains a single string `s`. --- ## Output Format Return a single integer representing the minimum number of character insertions required to make `s` a palindrome. --- ## Constraints * `0 ≤ len(s) ≤ 2000` * `s` consists only of lowercase English letters. --- ## Sample Case 0 ### Sample Input 0 ``` ab ``` ### Sample Output 0 ``` 1 ``` --- ## Function Signature ```cpp int minInsertions(string s) ``` **Return** Return an integer representing the minimum number of insertions required to make the given string a palindrome."