Minimum String Palindrome

editorial
, ,
1

Problem Link: SHPAL

Problem Statement:

Aman likes different types of string in which he wants every string to be palindrome, your task is to find the minimum string to be inserted every time in the front of string to make the given string palindrome. If the given string is palindrome print 0 else print the minimum string length to be inserted.
Note: String will be of any length and it will be of small characters only (a-z).

Input:

The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains the string .

Output:

Print the minimum Insertion to make the string palindrome else 0.

Sample Input :
2
lol
abcd

Sample Output :
0
3

Explanation:

  1. lol is already a palindrome that’s why O/P will be “0”
  2. To make “abcd” a palindrome we have to add “dcb” in front of “abcd” → “dcbabcd” . therefore 3 will be the O/P.

Solution:
#include <bits/stdc++.h>

using namespace std;

bool isPalin(string str, int st, int end)

{

    while (st < end)

    {

        if (str[st] != str[end])

            return false;

        st++;

        end--;

    }

    return true;

}
int findMinInsert(string str, int n)

{
    for (int i=n-1; i>=0; i--)

    {        

        if (isPalin(str, 0, i))

            return (n-i-1);

    }

}

int main()

{

    char Input[] = "abcd";

    int t;

    cin>>t;

    while (t--)

    {

        string s;

        cin>>s;

        printf("%d\n", findMinInsert(s, s.length()));
    }

    return 0;

}
1 Like