Problem

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 10^9 + 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.

Examples

Example 1

1
2
3
4

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

1
2
3

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

Constraints

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

Solution

Method 1 – Top-Down Dynamic Programming with Memoization

Intuition

The problem asks for the count of distinct palindromic subsequences. Since subsequences can overlap and repeat, we need to avoid double-counting. By using DP with memoization, we can efficiently count unique palindromic subsequences in all substrings, leveraging overlapping subproblems.

Approach

  1. Define a recursive function dp(l, r) that returns the number of distinct palindromic subsequences in the substring s[l:r+1].
  2. Use memoization to cache results for each (l, r) to avoid recomputation.
  3. For each character ch in 'a'..'d':
  • Find the first (i) and last (j) occurrence of ch in s[l:r+1].
  • If i > j, skip (character not present).
  • If i == j, only one palindromic subsequence: the single character.
  • If i < j, count two palindromic subsequences (ch and ch...ch), plus all palindromic subsequences inside s[i+1:j].
  1. Sum the counts for all characters and return the result modulo 10^9+7.
  2. Base case: if l > r, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
   int countPalindromicSubsequences(std::string s) {
      const int mod = 1e9 + 7, n = s.size();
      std::vector<std::vector<int>> memo(n, std::vector<int>(n, -1));
      std::function<int(int, int)> dp = [&](int l, int r) -> int {
        if (l > r) return 0;
        if (memo[l][r] != -1) return memo[l][r];
        int ans = 0;
        for (char ch = 'a'; ch <= 'd'; ++ch) {
           int i = l, j = r;
           while (i <= r && s[i] != ch) ++i;
           while (j >= l && s[j] != ch) --j;
           if (i > j) continue;
           if (i == j) ans = (ans + 1) % mod;
           else ans = (ans + 2 + dp(i + 1, j - 1)) % mod;
        }
        return memo[l][r] = ans;
      };
      return dp(0, n - 1);
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

func countPalindromicSubsequences(s string) int {
   mod := int(1e9 + 7)
   n := len(s)
   memo := make([][]int, n)
   for i := range memo {
      memo[i] = make([]int, n)
      for j := range memo[i] {
        memo[i][j] = -1
      }
   }
   var dp func(int, int) int
   dp = func(l, r int) int {
      if l > r {
        return 0
      }
      if memo[l][r] != -1 {
        return memo[l][r]
      }
      ans := 0
      for ch := byte('a'); ch <= 'd'; ch++ {
        i, j := l, r
        for i <= r && s[i] != ch {
           i++
        }
        for j >= l && s[j] != ch {
           j--
        }
        if i > j {
           continue
        }
        if i == j {
           ans = (ans + 1) % mod
        } else {
           ans = (ans + 2 + dp(i+1, j-1)) % mod
        }
      }
      memo[l][r] = ans
      return ans
   }
   return dp(0, n-1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
   public int countPalindromicSubsequences(String s) {
      int mod = 1000000007, n = s.length();
      Integer[][] memo = new Integer[n][n];
      return dp(0, n - 1, s, memo, mod);
   }
   private int dp(int l, int r, String s, Integer[][] memo, int mod) {
      if (l > r) return 0;
      if (memo[l][r] != null) return memo[l][r];
      int ans = 0;
      for (char ch = 'a'; ch <= 'd'; ch++) {
        int i = l, j = r;
        while (i <= r && s.charAt(i) != ch) i++;
        while (j >= l && s.charAt(j) != ch) j--;
        if (i > j) continue;
        if (i == j) ans = (ans + 1) % mod;
        else ans = (ans + 2 + dp(i + 1, j - 1, s, memo, mod)) % mod;
      }
      memo[l][r] = ans;
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
   fun countPalindromicSubsequences(s: String): Int {
      val mod = 1_000_000_007
      val n = s.length
      val memo = Array(n) { IntArray(n) { -1 } }
      fun dp(l: Int, r: Int): Int {
        if (l > r) return 0
        if (memo[l][r] != -1) return memo[l][r]
        var ans = 0
        for (ch in 'a'..'d') {
           var i = l
           var j = r
           while (i <= r && s[i] != ch) i++
           while (j >= l && s[j] != ch) j--
           if (i > j) continue
           if (i == j) ans = (ans + 1) % mod
           else ans = (ans + 2 + dp(i + 1, j - 1)) % mod
        }
        memo[l][r] = ans
        return ans
      }
      return dp(0, n - 1)
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
   def countPalindromicSubsequences(self, s: str) -> int:
      mod: int = 10 ** 9 + 7
      n: int = len(s)
      memo: list[list[int]] = [[-1] * n for _ in range(n)]
      def dp(l: int, r: int) -> int:
        if l > r:
           return 0
        if memo[l][r] != -1:
           return memo[l][r]
        ans: int = 0
        for ch in 'abcd':
           i, j = l, r
           while i <= r and s[i] != ch:
              i += 1
           while j >= l and s[j] != ch:
              j -= 1
           if i > j:
              continue
           if i == j:
              ans = (ans + 1) % mod
           else:
              ans = (ans + 2 + dp(i + 1, j - 1)) % mod
        memo[l][r] = ans
        return ans
      return dp(0, n - 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
   pub fn count_palindromic_subsequences(s: String) -> i32 {
      const MOD: i32 = 1_000_000_007;
      let n = s.len();
      let s = s.as_bytes();
      let mut memo = vec![vec![-1; n]; n];
      fn dp(l: usize, r: usize, s: &[u8], memo: &mut Vec<Vec<i32>>) -> i32 {
        if l > r { return 0; }
        if memo[l][r] != -1 { return memo[l][r]; }
        let mut ans = 0;
        for &ch in b"abcd" {
           let mut i = l;
           let mut j = r;
           while i <= r && s[i] != ch { i += 1; }
           while j >= l && s[j] != ch {
              if j == 0 { break; }
              j -= 1;
           }
           if i > j { continue; }
           if i == j { ans = (ans + 1) % MOD; }
           else {
              let inner = if i + 1 <= j.saturating_sub(1) {
                dp(i + 1, j - 1, s, memo)
              } else { 0 };
              ans = (ans + 2 + inner) % MOD;
           }
        }
        memo[l][r] = ans;
        ans
      }
      dp(0, n - 1, s, &mut memo)
   }
}

Complexity

  • ⏰ Time complexity: O(n^3)
  • 🧺 Space complexity: O(n^2)

Method 2 – Bottom-Up Dynamic Programming (Tabulation)

Intuition: Instead of solving subproblems recursively, we can fill a DP table iteratively for all substrings. For each substring, we count palindromic subsequences by considering the contribution of each character and using previously computed results for smaller substrings.

Approach:

  1. Let dp[i][j] be the number of different palindromic subsequences in s[i..j].
  2. Initialize dp[i][i] = 1 for all i (single characters are palindromic).
  3. For substrings of increasing length (len from 2 to n):
  • For each substring s[i..j]:
    • For each character ch in 'a'..'d':
    • Find the first (l) and last (r) occurrence of ch in s[i..j].
    • If l > r, skip.
    • If l == r, add 1 (single character).
    • If l < r, add 2 (for ch and ch...ch) plus dp[l+1][r-1] (palindromes inside).
    • Sum for all ch and take modulo.
  1. Return dp[0][n-1] as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
   int countPalindromicSubsequences(std::string s) {
      int n = s.size(), mod = 1e9 + 7;
      std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
      for (int i = 0; i < n; ++i) dp[i][i] = 1;
      for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
           int j = i + len - 1, ans = 0;
           for (char ch = 'a'; ch <= 'd'; ++ch) {
              int l = i, r = j;
              while (l <= j && s[l] != ch) ++l;
              while (r >= i && s[r] != ch) --r;
              if (l > r) continue;
              if (l == r) ans = (ans + 1) % mod;
              else ans = (ans + 2 + dp[l + 1][r - 1]) % mod;
           }
           dp[i][j] = ans;
        }
      }
      return dp[0][n - 1];
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func countPalindromicSubsequences(s string) int {
   n, mod := len(s), int(1e9+7)
   dp := make([][]int, n)
   for i := range dp {
      dp[i] = make([]int, n)
      dp[i][i] = 1
   }
   for l := 2; l <= n; l++ {
      for i := 0; i+l-1 < n; i++ {
        j, ans := i+l-1, 0
        for ch := byte('a'); ch <= 'd'; ch++ {
           left, right := i, j
           for left <= j && s[left] != ch {
              left++
           }
           for right >= i && s[right] != ch {
              right--
           }
           if left > right {
              continue
           }
           if left == right {
              ans = (ans + 1) % mod
           } else {
              inner := 0
              if left+1 <= right-1 {
                inner = dp[left+1][right-1]
              }
              ans = (ans + 2 + inner) % mod
           }
        }
        dp[i][j] = ans
      }
   }
   return dp[0][n-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
   public int countPalindromicSubsequences(String s) {
      int n = s.length(), mod = 1000000007;
      int[][] dp = new int[n][n];
      for (int i = 0; i < n; i++) dp[i][i] = 1;
      for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
           int j = i + len - 1, ans = 0;
           for (char ch = 'a'; ch <= 'd'; ch++) {
              int l = i, r = j;
              while (l <= j && s.charAt(l) != ch) l++;
              while (r >= i && s.charAt(r) != ch) r--;
              if (l > r) continue;
              if (l == r) ans = (ans + 1) % mod;
              else ans = (ans + 2 + dp[l + 1][r - 1]) % mod;
           }
           dp[i][j] = ans;
        }
      }
      return dp[0][n - 1];
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
   fun countPalindromicSubsequences(s: String): Int {
      val n = s.length
      val mod = 1_000_000_007
      val dp = Array(n) { IntArray(n) }
      for (i in 0 until n) dp[i][i] = 1
      for (len in 2..n) {
        for (i in 0..n - len) {
           val j = i + len - 1
           var ans = 0
           for (ch in 'a'..'d') {
              var l = i
              var r = j
              while (l <= j && s[l] != ch) l++
              while (r >= i && s[r] != ch) r--
              if (l > r) continue
              if (l == r) ans = (ans + 1) % mod
              else ans = (ans + 2 + dp[l + 1][r - 1]) % mod
           }
           dp[i][j] = ans
        }
      }
      return dp[0][n - 1]
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
   def countPalindromicSubsequences(self, s: str) -> int:
      n: int = len(s)
      mod: int = 10 ** 9 + 7
      dp: list[list[int]] = [[0] * n for _ in range(n)]
      for i in range(n):
        dp[i][i] = 1
      for length in range(2, n + 1):
        for i in range(n - length + 1):
           j: int = i + length - 1
           ans: int = 0
           for ch in 'abcd':
              l, r = i, j
              while l <= j and s[l] != ch:
                l += 1
              while r >= i and s[r] != ch:
                r -= 1
              if l > r:
                continue
              if l == r:
                ans = (ans + 1) % mod
              else:
                inner = dp[l + 1][r - 1] if l + 1 <= r - 1 else 0
                ans = (ans + 2 + inner) % mod
           dp[i][j] = ans
      return dp[0][n - 1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

impl Solution {
   pub fn count_palindromic_subsequences(s: String) -> i32 {
      const MOD: i32 = 1_000_000_007;
      let n = s.len();
      let s = s.as_bytes();
      let mut dp = vec![vec![0; n]; n];
      for i in 0..n {
        dp[i][i] = 1;
      }
      for len in 2..=n {
        for i in 0..=n - len {
           let j = i + len - 1;
           let mut ans = 0;
           for &ch in b"abcd" {
              let mut l = i;
              let mut r = j;
              while l <= j && s[l] != ch { l += 1; }
              while r >= i && s[r] != ch {
                if r == 0 { break; }
                r -= 1;
              }
              if l > r { continue; }
              if l == r {
                ans = (ans + 1) % MOD;
              } else {
                let inner = if l + 1 <= r.saturating_sub(1) {
                   dp[l + 1][r - 1]
                } else { 0 };
                ans = (ans + 2 + inner) % MOD;
              }
           }
           dp[i][j] = ans;
        }
      }
      dp[0][n - 1]
   }
}

Complexity

  • ⏰ Time complexity: O(N^3)
  • 🧺 Space complexity: O(N^2)