Last Updated: 26 May, 2021
Remove All The Palindromes
Moderate
Asked in companies
Sushant is learning about palindromes. One day his teacher gave him a string ‘STR’ consisting of only the lowercase letters and asked him to modify the string in such a way that the string doesn’t contain any palindromic substring by replacing the minimum characters present in the given string. Sushant, although a brilliant student, needs your help.
Note:
A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward, such as “madam” or “racecar”.
Example:
Given an ‘STR’: ‘aaaaaaa’ The minimum characters that will be replaced are 4. The string can be converted into ‘abcabca’.
Note:
Here are multiple possible answers, for example changing all the elements, but we have to find the minimum replacements possible.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a string that represents the input string ‘STR’.
Output Format:
For each test case, print an integer denoting the minimum characters that can be replaced such that the string does not contain any palindromic substring of length 1.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 10^2
1 <= |STR| <= 10^3
Time Limit: 1 sec
Approaches
The basic idea of this approach is to remove all the palindromes of length two and three. The idea is that if there exists a palindromic substring larger than length 3 then a palindrome of length 2 or 3 is present.
Here is the algorithm:
- Declare a variable ‘COUNT’ which stores the minimum number of replacements.
- Declaring another variable ‘CHANGECHAR’ which will store the ASCII value of capital letters we can use to replace the character in the given string in order to remove the palindromes.
- Iterate over the given string ‘STR’ from ‘I’ = 0 to ‘I’ = length - 1 :
- If the ‘Ith’ element is equal to the ‘I+1th’ element then increment ‘COUNT’ by 1 and replace the next character with a different element. As the given string is lowercase, replace the character with a capital letter.
- Else if a palindrome of length ‘3’ is found, then replace the next character and increment ‘COUNT.’
- Finally, return ‘COUNT’.