Remove All The Palindromes

Moderate
0/80
profile
Contributed by
12 upvotes
Asked in companies
AmazonFlipkart limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
abcdefg
abcbaxxy
Sample Output 1:
0
2
Explanation For Sample Input 1:
In the first test case, the number of replaced characters is 0. As there are no substrings present in the given string, hence the answer is 0.

In the second test case, the number of replaced characters is 4. Here, the modified string can become abczaxqy
Sample Input 2:
2
racecar
plattoonp
Sample Output 2:
1
2
Explanation For Sample Input 2:
In the first test case, the number of replaced characters is 1. Here the string can be modified into racZcar

In the second test case, the number of replaced characters is 2. Here the string can be modified into plataoXnp
Hint

Greedily remove the palindromes of length two and three.

Approaches (1)
Greedy Approach

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:

 

  1. Declare a variable ‘COUNT’ which stores the minimum number of replacements.
  2. 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.
  3. 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.’
  4. Finally, return ‘COUNT’.
Time Complexity

O(N), where N is the size of the string given ‘STR’.

 

As we are iterating over the string once and visiting all the string characters, the time complexity is O(N).

Space Complexity

O(1), 

 

Because we are not using any extra space for finding our answer.

Code Solution
(100% EXP penalty)
Remove All The Palindromes
Full screen
Console