Count Palindromic Subsequences

Hard
0/120
Average time to solve is 20m
profile
Contributed by
36 upvotes
Asked in company
BNY Mellon

Problem statement

A subsequence of a string is achieved by removing some (possibly 0) characters without changing the order of the remaining characters.


You have been given a string 's'.


Find the number of non-empty palindromic subsequences (not necessarily be distinct) in string 's' and return that number modulo 10 ^ 9 + 7.


Example : 
Input: 's' = "pqqr"

Output: 5

Explanation: The subsequences are:

p

q

q

r

qq

Please note that both "q" are considered different.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a string 's'.


Output Format : 
Print the number of non-empty palindromic subsequences modulo 10 ^ 9 + 7.


Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1 :
pqqr


Sample output 1 :
5


Explanation of Sample output 1 :
The subsequences are:
p
q
q
r
qq
Please note that both "q" are considered different.


Sample Input 2 :
abc


Sample output 2 :
3


Sample Input 3:
aaaa


Sample Output 3:
15


Expected time complexity :
The expected time complexity is O(|s| ^ 2).


Constraints :
1 <= |s| <= 1000

Where |s| denotes the length of 's'.

Time limit: 1 sec
Hint

Can you think of breaking the problem into sub-problems?

Approaches (3)
Recursive brute force

The basic idea of this approach is to break the original problem into sub-problems. Let us assume we want to find the number of palindromic subsequences in string 's' whose length is |s|.

Now, let us define a recursive function 

count(int i, int j, string &s)

Which returns the number of palindromic subsequences in the substring [i:j] of string 's'. 

Now, consider the following steps :

  1. If ('i' == 'j') then return 1 because every single character in the string is a palindrome itself.
  2. If ('s[i]' == 's[j]') then we need to add the following three terms to get the count:

We can append 's[i]' and 's[j]' at the front and back respectively in any palindromic subsequence of substring [i + 1, j - 1] and generate a new palindromic subsequence i.e. add count(i + 1, j - 1, s) + 1. Note 1 is added because a pair of characters ('s[i]', 's[j]') will make a palindrome.

  • And also we need to add all the palindromic subsequences containing the ith and jth element separately i.e. count(i + 1, j, s) + count(i, j - 1, s) - count(i + 1, j - 1, s). We need to subtract the count of the substring [i + 1, j - 1] as it was added twice.
  • After adding all the terms from the above points, return 1 + count(i, j - 1, s) + count(i + 1, j, s).
  1. Otherwise ('s[i]' != 's[j]'), since the current two characters ('s[i]' and 's[j]') can’t be added, check the rest of sub-sequences i.e. return count(i, j - 1, s) + count(i + 1, j, s) - count(i + 1, j - 1, s). Note that count(i + 1, j - 1, s) is subtracted because it was added twice.
Time Complexity

O(2 ^ |s|), Where |s| denotes the length of the string 's'.

Since we are using a recursive function that may check all subsequences of the given string. So the overall time complexity will be O(2 ^ |s|).

Space Complexity

O(|s|), Where |s| denotes the length of the string 's'.

Since we are using a recursive function where there may be |s| states present in the recursive call stack in the worst case. So the overall space complexity will be O(|s|).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count Palindromic Subsequences
Full screen
Console