Fewest Insertions Needed for a Palindrome

### Problem Insert any character at any string position in one operation. Return the minimum operations required to turn s into a palindrome, a string equal to its reversal. Original characters cannot be removed or reordered. ```cpp class Solution { public: int minInsertions(string s); }; ``` ### Examples **Example 1:** ```text Input: s = "abca" Output: 1 Explanation: Inserting b before the final a yields abcba; the original string is not already a palindrome. ``` **Example 2:** ```text Input: s = "abcd" Output: 3 Explanation: Appending cba gives abcdcba. With four distinct original letters, at most one can be unpaired at the center, so at least three new matching letters are needed. ``` ### Constraints - s contains 1 to 500 lowercase English letters. ### Contract considerations Inserted letters may go at either endpoint or inside the current string. ```hint Read the boundary condition Account for an already palindromic string and for insertions inside the string as well as at its ends. Original characters retain their order. ``` ### Boundary reminders Inserted letters may go at either endpoint or inside the current string.