155. Count Palindromic Partitions of a String

Given a string s, count the number of distinct ways to partition it into one or more contiguous substrings such that every substring is a palindrome.

Input: A single line containing the string s. Output: Print a single integer - the number of ways to partition s into palindromic substrings.

1 <= |s| <= 200

This is the 'count' version of 'Print All Palindromic Partitions' - the same recursive structure, but returning a count instead of building and collecting every actual partition, which is exactly what makes memoization straightforward here (you can't easily memoize a list of ALL partitions the same way you can memoize a simple count).

Count how many distinct ways a string can be split into pieces where every piece is itself a palindrome. Brute force: Try every possible way to insert cut points across the whole string and check if EVERY resulting piece is a palindrome - this checks partitions combinatorially without pruning early, and re-checks the same substring's palindrome status repeatedly across different partition attempts. Optimised: Precomputing a DP table of 'is substring [i,j] a palindrome' ONCE (in O(n²)) turns every palindrome check during the counting recursion into an O(1) lookup instead of an O(n) re-verification - combined with memoizing the COUNT of ways to partition each suffix, this avoids the exponential blowup of naive recursive counting.

Use backtracking: at each position, try every prefix of the remaining suffix, check (from scratch) whether it is a palindrome, and if so recurse on what's left, counting a valid partition whenever the recursion consumes the whole string. This explores every possible partition and is correct, but re-checking palindromes character by character inside an already-exponential search makes it very slow. Time: O(2^n * n) Space: O(n)

Precompute nothing extra, but memoize the recursive function on the starting index, so that count(i) (the number of palindromic partitions of the suffix starting at i) is computed once and reused instead of being recomputed for every path that reaches index i. Palindrome checks are still done naively per substring, so the work is bounded by the number of distinct (start, end) substring checks across all recursive calls, a large improvement over the un-memoized exponential blowup. Time: O(n^3) Space: O(n^2)

First build a 2D boolean table isPal[i][j] marking whether s[i..j] is a palindrome, filled in O(1) per cell using the fact that s[i..j] is a palindrome exactly when s[i] equals s[j] and s[i+1..j-1] is a palindrome. Then compute dp[i] = number of ways to partition s[0..i-1], where dp[i] = sum of dp[j] over all j < i such that s[j..i-1] is a palindrome (an O(1) lookup now). Combining the two removes the repeated substring recomputation entirely, giving quadratic time overall. Time: O(n^2) Space: O(n^2)

1. Try every possible FIRST cut, but only recurse into it if the piece before the cut is itself a palindrome. 2. Recursively count the ways to partition the remaining suffix the same way, summing contributions from every valid first cut. 3. Precomputing which substrings are palindromes with a DP table upfront avoids re-checking the same range's palindrome-ness repeatedly.

Time: O(n²) with both the palindrome-precomputation table and memoized partition-counting. Space: O(n²) for the palindrome table, plus O(n) for the memoized counts array.

Test |s| = 1 (always 1 way), a string made of one repeated character (many palindromic partitions), and |s| = 200 for performance.

Be ready to explain the TWO layers of optimization here (precomputed palindrome table, AND memoized partition counts) - using only one without the other still leaves real inefficiency on the table.