Scale Engineer

Count Different Palindromic Subsequences

Hard
#0684Time: O(N * 2^N). There are `2^N` subsequences. For each, palindrome checking and set insertion take time proportional to its length (up to O(N)).Space: O(N * 2^N). The recursion depth is O(N). The set can store up to `2^N` subsequences, each of average length O(N).
Patterns
Dynamic Programming
Data structures
String

Prompt

Given a string s, return the number of different non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 109 + 7.

A subsequence of a string is obtained by deleting zero or more characters from the string.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences a1, a2, ... and b1, b2, ... are different if there is some i for which ai != bi.

 

Example 1:

Input: s = "bccb"
Output: 6
Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Example 2:

Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
Output: 104860361
Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 109 + 7.

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either 'a', 'b', 'c', or 'd'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible non-empty subsequence of the given string s. For each generated subsequence, we check if it is a palindrome. To count only the unique palindromic subsequences, we store them in a hash set. The final answer is the size of this set.

Algorithm

  • Initialize an empty HashSet<String> called palindromes.
  • Define a recursive function generate(index, currentSubsequence).
  • Base Case: If index reaches the end of the string:
    • If currentSubsequence is not empty and is a palindrome, add it to the palindromes set.
    • Return.
  • Recursive Step:
    • Call generate(index + 1, currentSubsequence) (character at index is not included).
    • Call generate(index + 1, currentSubsequence + s.charAt(index)) (character at index is included).
  • Start the process by calling generate(0, "").
  • The answer is palindromes.size(). Note that this approach is not feasible for the given constraints and does not handle the modulo arithmetic.

Walkthrough

We can use a recursive helper function to generate all subsequences. The function would take the current index and the subsequence built so far. At each index i, we have two choices: either include the character s[i] in the current subsequence or not. This leads to 2^N total subsequences. The base case for the recursion is when we have traversed the entire string. At this point, if the generated subsequence is non-empty, we check if it's a palindrome. A palindrome check for a string of length k can be done in O(k) time. A HashSet<String> is used to store the unique palindromic subsequences found. The final result is the size of the set. This method is too slow for the problem's constraints but serves as a conceptual starting point.

import java.util.HashSet;import java.util.Set; class Solution {    Set<String> palindromes = new HashSet<>();    String s;    int n;     // This method is for illustration and will Time Limit Exceed.    public int countPalindromicSubsequences(String s) {        this.s = s;        this.n = s.length();        generate(0, new StringBuilder());        return palindromes.size();    }     private void generate(int index, StringBuilder current) {        if (index == n) {            if (current.length() > 0 && isPalindrome(current.toString())) {                palindromes.add(current.toString());            }            return;        }         // Exclude s.charAt(index)        generate(index + 1, current);         // Include s.charAt(index)        current.append(s.charAt(index));        generate(index + 1, current);        current.deleteCharAt(current.length() - 1); // backtrack    }     private boolean isPalindrome(String str) {        int left = 0, right = str.length() - 1;        while (left < right) {            if (str.charAt(left) != str.charAt(right)) {                return false;            }            left++;            right--;        }        return true;    }}

Complexity

Time

O(N * 2^N). There are `2^N` subsequences. For each, palindrome checking and set insertion take time proportional to its length (up to O(N)).

Space

O(N * 2^N). The recursion depth is O(N). The set can store up to `2^N` subsequences, each of average length O(N).

Trade-offs

Pros

  • Simple to understand and conceptualize.

Cons

  • Extremely inefficient and will time out for the given constraints (N <= 1000).

  • High space complexity due to storing all unique palindromic subsequences and the recursion stack.

  • Not practical for problems requiring modulo arithmetic on a large result.

Solutions

class Solution {private  final int MOD = (int)1 e9 + 7;public  int countPalindromicSubsequences(String s) {    int n = s.length();    long[][][] dp = new long[n][n][4];    for (int i = 0; i < n; ++i) {      dp[i][i][s.charAt(i) - 'a'] = 1;    }    for (int l = 2; l <= n; ++l) {      for (int i = 0; i + l <= n; ++i) {        int j = i + l - 1;        for (char c = 'a'; c <= 'd'; ++c) {          int k = c - 'a';          if (s.charAt(i) == c && s.charAt(j) == c) {            dp[i][j][k] = 2 + dp[i + 1][j - 1][0] + dp[i + 1][j - 1][1] +                          dp[i + 1][j - 1][2] + dp[i + 1][j - 1][3];            dp[i][j][k] %= MOD;          } else if (s.charAt(i) == c) {            dp[i][j][k] = dp[i][j - 1][k];          } else if (s.charAt(j) == c) {            dp[i][j][k] = dp[i + 1][j][k];          } else {            dp[i][j][k] = dp[i + 1][j - 1][k];          }        }      }    }    long ans = 0;    for (int k = 0; k < 4; ++k) {      ans += dp[0][n - 1][k];    }    return (int)(ans % MOD);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem