Count Palindrome Partitions

Problem

Count the number of ways to partition the string s so that every part is a palindrome. Parts may repeat and every character must be used.

Precompute the palindrome table for all substrings, then let dp[i] be the number of ways to split the prefix of length i, accumulating dp[j] whenever s[j:i] is a palindrome. The empty string has zero partitions.

Hint

dp[i] sums dp[j] over every j where the suffix from j to i - 1 is a palindrome.

Test cases

case 1

in: ["aab"]

expected: 2

case 2

in: ["ab"]

expected: 1

case 3

in: ["aaa"]

expected: 4

case 4

in: ["aabb"]

expected: 4

case 5

in: [""]

expected: 0

Starter codePython

def count_palindrome_partitions(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor