PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
DIFFICULTY:
SIMPLE
PREREQUISITES:
Bitmasking
PROBLEM:
Given a string, find the minimum number of characters to remove from it to make it a palindrome.
QUICK EXPLANATION:
Generate all subsequences of the string using bitmasking and calculate least number of characters to be removed to make it a palindrome.
EXPLANATION:
Since the constraint for the length of string is less than 20, we can use bitmasking. Using bitmasking we generate all sequences of subsequences of the string and check if those subseqences are palindrome. After which we find the subsequence where least number of characters are to be removed from the original string.
SOLUTIONS:
Setter's Solution
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
string now=Console.ReadLine();
int min=int.MaxValue;
for(int i=0;i<(1<<now.Length);i++)
{
string temp="";
for(int j=0;j<now.Length;j++)
{
if((i&(1<<j))!=0)
{
temp+=now[j];
}
}
char [] cc=temp.ToCharArray();
Array.Reverse(cc);
if(new string(cc)==temp)
{
min=Math.Min(min,now.Length-temp.Length);
}
}
Console.WriteLine(min);
}
}