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)