Count Palindromic Subsequences - II

Hard
0/120
profile
Contributed by
6 upvotes
Asked in companies
FacebookLinkedInApple

Problem statement

You have been given a string ‘S’. Your task is to find the number of non-empty distinct palindromic subsequences in string ‘S’ and return that number modulo 10^9 + 7.

Note:

1. A string ‘A’ is a subsequence of a string ‘B’ if ‘A’ can be obtained from ‘B’ by deleting several (possibly, zero or all) characters. 
2. A sequence is palindromic if it is equal to the sequence reversed.
3. Two sequences A1, A2,... and B1, B2,... are different if there is some ‘i’ for which ‘Ai’ != ‘Bi’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T’, denoting the number of test cases.

The first line of each test case contains a string ‘S’.
Output Format : 
For each test case, print the number of non-empty distinct palindromic subsequences modulo 10^9 + 7.

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 <= |S| <= 3*10^3

Where |S| denotes the length of ‘S’.

Time limit: 1 sec
Sample Input 1 :
2
abc
pppp
Sample output 1 :
3
4
Explanation For Sample Output 1 :
For the first test case, distinct palindromic subsequences are “a”, “b”, and “c”.

For the second test case, distinct palindromic subsequences are “p”, “pp”, “ppp”, “pppp”.
Sample Input 2 :
2
aba
pqqr
Sample output 2 :
4
4
Hint

Check for every possible subsequence present in the string. 

Approaches (3)
Brute Force

The basic idea is to find all the subsequences of the string and check whether they are palindrome or not. For each character of the string we have two choices with us:

  1. Include it in the current sequence.
  2. Exclude it in the current sequence.

We also use a set to store the distinct subsequences and print the size of the set minus 1 (empty subsequence).

 

Here is the algorithm:

 

  1. Create an unordered set (say, ‘ST’) to store the distinct subsequences.
  2. Call the function HELPER to find the subsequences.
  3. Return the size of ‘ST’ minus 1.

 

HELPER(‘S’, ‘IDX’, ‘ST’, ‘CURR’)   (where ‘S’ is the given string, ‘IDX’ is the current index, ‘ST’ is the set, ‘CURR’ is the current subsequence which is initialized to “”).

 

  1. Base case:
    • Check if ‘IDX’ is the size of the ‘S’.
      • Check if ‘CURR’ is a palindrome.
        • Insert ‘CURR’ in ‘S’.
      • Return.
  2. Call the HELPER function recursively by excluding the current character.

Similarly, call the HELPER function again by including the current character (‘CURR’ + ‘S[IDX]’).

Time Complexity

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

 

Every character of the string has two choices, whether to include it in a subsequence or not. There are total ‘N’ characters, so the number of possible combinations will be 2 * 2 * 2… (‘N’ times). And for every subsequence, we check whether it is palindrome or not, which takes O(N) time. Therefore, the overall time complexity will be O((2 ^ N) * N).

Space Complexity

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

The recursive stack for the HELPER function can contain at most the length of the string. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Count Palindromic Subsequences - II
Full screen
Console