Last Updated: 15 Sep, 2021

Palindrome Count

Hard

Asked in companies

Solve now

Problem statement

Ninja loves to play with strings and anagrams. A palindrome is a string that is read the same backward or forward. An anagram is a string that is formed by rearranging the characters of the string. Ninjas have been given a string ‘STR’, and asked to find the number of substrings whose anagram is palindromic.

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains a string ‘STR’.

Output Format :

For each test case, print a single integer representing the number of palindromes.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= |STR| <= 5*10^3
The string ‘STR’ contains small letters only.   

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The basic idea is to find all the substrings of the string, and for each substring, find whether any anagram of the substring is palindrome or not. The substring is palindrome or not if the frequency of all the characters except at most one character must be even.

Here is the algorithm :

Create a variable (say, ‘RES’) used to store the number of palindromes.
Run a loop from 0 to the length of the string (say, iterator ’i’)
1. Run a loop from ‘i’ to the length of the string (say, iterator ‘j’)
  1. Check whether the substring present between ‘i’ to ‘j’ is palindrome or not by finding the frequency of each character, increment ‘RES’ by 1.
Finally, return ‘RES’.

Solve now

02 Approach

The idea is to generate the masks of 26 characters as there can be a maximum of 26 characters and to count the number of palindromes.

Here is the algorithm :

Create a variable (say, ‘RES’) used to store the number of palindromes.
Run a loop from 0 to the length of the string (say, iterator ’i’)
- Create a variable (say, ‘MASK’) used to find the bit mask of the substring.
- Run a loop from ‘i’ to the length of the string (say, iterator ‘j’)
  - Create a variable (say, ‘TEMP’) and set the current character in it.
  - Do the bitwise XOR of ‘TEMP’ and ‘MASK’ where each bit represents the frequency of each 26 characters,
  - Check if bitwise and ‘MASK’ and ‘MASK’ - 1 is equal to 0, increment ‘RES’ by 1.
Finally, return ‘RES’.

Solve now

03 Approach

The idea is similar to approach 2, but we will be using a map to store the frequencies of the masks to avoid another traversing of the string.

Here is the algorithm :

Create a variable (say, ‘RES’) used to store the number of palindromes.
Create an unordered map (say, ‘MP’) to store the masks.
Update masks of 0 to 1.
Create a variable (say, ‘TEMP’) and initialize it with 0.
Run a loop from 0 to the length of the string (say, iterator ’i’)
- Update ‘TEMP’ by bitwise XOR of ‘TEMP’ and set a bit of the current character.
- Update ‘RES’ by adding the value of ‘TEMP’ present in the map.
- Run a loop from 0 to 26 (say, iterator ‘j’) to calculate the mask of each character.
  - Update the “RES” by adding the frequencies of masks by doing bitwise xor of ‘TEMP’ and 2 to the power of ‘i’.
- Update the value of ‘TEMP’ in the map by incrementing it with 1.
Finally, return ‘RES’.

Solve now