PROBLEM ANALYSIS:
1. First we have to know how many palindromic substring are there in the string.
2. Then replace any character of the substrings to get minimum number of moves.
let us consider a string s= aauaavvu
Here we can see the palindromic substrings are as follows:
aa aauaa aa vv
Here, from the substring aauaa, we can conclude that if there is a palindromic substring P of length more than 3 is present then there must be palindromic substring of length 2 or 3 inside that substring. If we can remove the substrings of length 2 or 3, then automatically P will become non palindromic.
So, our main motto is to remove all palindromic substring of length 2 or 3. (remove in a sense of making non palindromic).
ALGORITHM:
1. Create an array of bool type of size of the string size and mark all the elements as false to signify that initially no elements are replaced. The easy way to do that is to use memset function or you can iterate the whole array and assign each element as 'false'.
2. Now, traverse the string to find palindromic substring of length 2 or 3 and mark the last character of the substring as used i.e. assign true in the array. If there is a substring of length 2 inside a substring of length 3, mark only one of them (conditions applied though) and increment your count.
3. The time complexity of this algorithm is O(n).
CODE:
#include <bits/stdc++.h>
using namespace std;
int main()
{ ios_base::sync_with_stdio(false); //to make the code faster, no relation with the problem
cin.tie(NULL);
int t; //no of test cases
cin>>t;
while(t--)
{
//actual code starts here
string s;
cin>>s; //string is taken as user input
int n=s.length();
int c=0;
bool a[n]; //array to mark the elements as replaced
memset(a,false,sizeof(a)); //use loop to set the values as false if you're nt comfortable
int i=1;
while(i<n)
{
bool p=false; //to make sure that count is not done twice for one element
if(s[i-1]==s[i] && a[i-1]==false) //checking substring of length 2
{
p=true;
}
if(i>1 && s[i]==s[i-2] && a[i-2]==false) //checking substring of length 3
p=true;
a[i]=p;
c=c+a[i];
i++;
}
cout<<c<<endl;
}
return 0;
}
source of test cases; codeforces.com
0 Comments