Practice/Salesforce/Leetcode 730. Count Different Palindromic Subsequences

Leetcode 730. Count Different Palindromic Subsequences

CodingMust

Problem

Given a string containing only the characters 'a', 'b', 'c', and 'd', determine how many distinct non-empty palindromic subsequences exist within it. A subsequence is formed by deleting zero or more characters from the original string without changing the relative order of remaining characters. Two subsequences are considered distinct if they differ in at least one position.

Since the answer may be very large, return the result modulo 10^9 + 7.

Requirements

1. Count all distinct palindromic subsequences in the given string
2. A palindrome reads the same forwards and backwards
3. Subsequences maintain the original character order but can skip characters
4. Return the count modulo 1000000007 (10^9 + 7)
5. Handle strings with repeated characters without double-counting identical subsequences

Constraints

• 1 ≤ length of string ≤ 1000
• The string contains only characters from the set {'a', 'b', 'c', 'd'}
• Time complexity should be O(n²) or better
• Space complexity should be O(n²)

Examples

Example 1:

` Input: s = "bccb" Output: 6 Explanation: The 6 distinct palindromic subsequences are:

• 'b' (appears once as distinct subsequence)
• 'c' (appears once as distinct subsequence)
• 'bb'
• 'cc'
• 'bcb'
• 'bccb' `

Example 2:

Input: s = "abcdabcd" Output: 104 Explanation: Many palindromic subsequences can be formed, including single characters, pairs like 'aa', 'bb', and more complex patterns like 'abcba', 'abdba', etc.

Example 3:

Input: s = "a" Output: 1 Explanation: Only one palindromic subsequence: 'a'