Blind 75 · 1-D Dynamic Programming
Given a string s, count its palindromic substrings.
Substrings at different positions count separately even when their text is identical: "aaa" contains six — three single a's, two "aa"s, and "aaa" itself.
Example 1: Input: s = "abc" Output: 3 Explanation: only the three single characters. Example 2: Input: s = "aaa" Output: 6 Example 3: Input: s = "aba" Output: 4 Explanation: a, b, a, and "aba". Example 4: Input: s = "aabb" Output: 6
1 <= s.length <= 1000 s consists of lowercase English letters.
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence.
Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
Identical machinery to Longest Palindromic Substring, with the maximum replaced by a tally: every successful expansion step IS one more palindromic substring. If you solved that problem first, say so — this is a two-line edit, and noticing that is worth more than rederiving it.
1. For each of the 2n-1 centres, expand while the ends match.
2. Count one for every step that matches.
Time O(n^2). Space O(1).