Make a palindrome

Besides a possible lone letter in the middle, the palindrome will contain two of every letter, as there is only one $B, A, N, T, F, O,$ and $V$ , we will have to add at least $6$ letters, $7$ if none of them are directly in the middle of the palindrome.

Observing what is left if we take these lone letters out we find $RILLIREER$ , and we want the maximum amount of symmetry which could happen from the middle of the $E$ 's or the middle of the $L$ 's. As there are more pairs of letters surrounding the $L$ 's these are most symmetric and it makes most sense to make the string palindromic about the middle of them.

Looking back at the original string, these letters are already together thus there will be an even number of each letter, we must add one of all the letters that are alone $7$ , as there are $3$ $R$ s originally we must add $1$ , and $2$ $e$ 's as there are $2$ initially on the right side of the palindromic divide. For a total of $7+1+2=\boxed{10}$ that must be added

C++ Solution using Dynamic Programming

Let dp[l][r] be the minimum number of insertions to make s[l...r] a palindrome.

If s[l] = s[r], then obviously dp[l][r] = dp[l + 1][r - 1] .

Otherwise, you must either add s[r] to the beginning or s[l] to the end so dp[l][r] = 1 + min(dp[l + 1][r], dp[l][r - 1]) .

#include <bits/stdc++.h>
using namespace std;

int findMinInsertions(string &s, int i, int j, map < pair<int, int>, int > &dp)
{
    if(i >= j)
        return 0;
    if(dp.count({i,j}))
        return dp[{i, j}];

    if(s[i] == s[j])
        return dp[{i,j}] = findMinInsertions(s, i+1, j-1, dp);
    else
        return dp[{i,j}] = 1 + min(findMinInsertions(s, i+1, j, dp), findMinInsertions(s, i, j-1, dp));
}

int main()
{
    int n = 16;    //Length of string

    string s = "Brilliantforever";

    map < pair <int, int>, int > dp;

    cout << findMinInsertions(s, 0, n-1, dp); 

    return 0;
}

Problem link : SPOJ

Approach : Codeforces blog

Dynamic Programming Algorithm - For any string to be a palindrome, the first and the last letters must be the same. So if they are currently not the same, one would have to insert a character either at the start or at the end. If they are the same, then one can move forward.

Also for a string to be a palindrome, the string with the first and last letter are removed must also be a palindrome. So one can write the following recursive equation - Minimum steps required to make a string palindrome = Steps required to make the last two letters same + Minimum steps required to make the inner string palindrome.

Applying this to the string "bacc" Step 1: b and c not equal : Add 1 b at the end. Move to the inward string now : "acc" a and c not equal : Add 1 a at the end. Move to the inward string now : "cc": Already a palindrome.

So 2 steps were required for "bacc". One can use the same algorithm for this question to get 10 steps.

breveroftnailliantforeverb