Palindrome Count

Hard
0/120
Average time to solve is 30m
profile
Contributed by
8 upvotes
Asked in companies
AdobeInfo Edge India (Naukri.com)

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
aa
abc
Sample Output 1 :
3
3
Explanation For Sample Input 1 :
For first test case :

Substring are: {a, a, aa}
Since, all the substrings are palindromes.
So, the result is 3.

For second test :

Substring are: {a, b, c, ab, bc, abc}
Since, all {a, b, c} are palindromes. And no anagram of {ab, bc, abc} have palindromes. 
So, the result is 3.
Sample Input 2 :
2
aaa
aab
Sample Output 2 :
6
5
Hint

Try checking for palindromes on all the substrings.

Approaches (3)
Brute Force

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 :

 

  1. Create a variable (say, ‘RES’) used to store the number of palindromes.
  2. 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.
  3. Finally, return ‘RES’.
Time Complexity

O(N ^ 3), where ‘N’ is the size of the string.

 

We traverse the whole string twice to generate all the substrings of the string, and for each substring, we check whether it is palindrome or not by traversing the substring again. Therefore, the overall time complexity will be O(N ^ 3).

Space Complexity

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

 

We store the count of all characters of the substring. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Palindrome Count
Full screen
Console