Count Special Palindromic Substrings

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
5 upvotes
Asked in companies
BarclaysAccolitePaxcom

Problem statement

You are given a string 'STR'. Your task is to count the number of special palindromic substrings of size greater than 1 that the given string contains. A substring is said to be a special palindrome in the following two cases:

If all the characters in the substring are the same.

If the length of the substring is odd and only the middle element is different, while all the other characters are the same.
Example: 
“aba” is a special palindrome, while “abaa” is not
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first and the only line of each test case contains the string 'STR'.
Output Format: 
For each test case, print the count of special palindromic substrings.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= |STR| <= 10000

Time limit: 1 sec
Sample Input 1:
2
bcbc
ccddd
Sample Output 1:
2
4
Explanation For Sample Input 1:
In the first test case, 
The special palindromic substrings in the given string are: bcb and cbc. Hence, the answer is 2 in this case.

In the second test case, 
The special palindromic substrings in the string are: cc, dd, ddd and dd. Hence, the answer is 4 in this case.
Sample Input 2:
2
abccdcdf
baabaab
Sample Output 2:
3
4
Hint

Can you think of checking each substring?

Approaches (2)
Brute Force

The basic approach is to create all possible substrings from the given string and then count the number of special palindromic substrings from them.

 

Algorithm:

 

  • Let N be the length of the given string.
  • Initialise a variable “count” with starting value ‘0’ to store the total count of special palindromic substrings.
  • Start creating the substrings of the given string using two loops,
  • The first loop points towards the starting point of the substring, i = 0 to N-1
    • The second loop points towards the ending point of substring, j = i + 1 to N-1
      • Start another loop that will check for all characters of the substring created
        • If all characters are the same.
        • Or if the length of the substring is odd and only the middle element is different.
        • If such string is found:
          • Increment “count” by 1.
    • Return the variable “count”.
Time Complexity

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

 

Since we are traversing through the complete string using three loops. Hence, the overall Time Complexity is O(N ^ 3).

Space Complexity

O(1)

 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Count Special Palindromic Substrings
Full screen
Console