Approach #1 Dynamic Programming (using 3D array) [Accepted]

Intuition and Algorithm

Let dp[x][i][j] be the answer for the substring S[i...j] where S[i] == S[j] == 'a'+x. Note that since we only have 4 characters a, b, c, d, thus 0 <= x < 4. The DP formula goes as follows:

• If S[i] != 'a'+x, then dp[x][i][j] = dp[x][i+1][j], note that here we leave the first character S[i] in the window out due to our definition of dp[x][i][j].

• If S[j] != 'a'+x, then dp[x][i][j] = dp[x][i][j-1], leaving the last character S[j] out.

• If S[i] == S[j] == 'a'+x, then dp[x][i][j] = 2 + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]. When the first and last characters are the same, we need to count all the distinct palindromes (for each of a,b,c,d) within the sub-window S[i+1][j-1] plus the 2 palindromes contributed by the first and last characters.

Let n be the length of the input string S, The final answer would be dp[0][0][n-1] + dp[1][0][n-1] + dp[2][0][n-1] + dp[3][0][n-1] mod 1000000007.

Example Walkthrough

Indeed this is a hard problem to solve and thoroughly understanding its solution is also challenging. Maybe the best way to understand the above approach is to walkthrough some simple examples to help build up intuitions.

Let's first look at the strategy we used to fill the DP table and then walkthrough a concrete example to see how it works.

!?!../Documents/730_Example_Walkthrough.json:1280,720!?!

Complexity Analysis

• Time complexity : $$O(N^2)$$ where $$N$$ is the length of the input string $$S$$ . It takes quadratic time to fill up the DP table.

• Space complexity : $$O(N^2)$$ where $$N$$ is the length of the input string $$S$$ . The DP table takes quadratic space.

Note that we ignore the constant factor $$4$$ in the above analysis.

Conclusion

As we look back, this problem reveals a key attribute which indicates that dynamic programming might be a good fit: overlapping sub-problems as we recall the DP formula. By practicing more problems, we can build up this kind of intuition.

Credit: the above solution is inspired by this post written by @elastico. His solution is space optimized. However, I found that my approach is relatively easy to understand for people who found this problem hard to approach.

Analysis written by: @imsure.

Approach #2: Dynamic Programming (using 2D array) [Accepted]

Intuition

Almost every palindrome is going to take one of these four forms: a_a, b_b, c_c, or d_d, where _ represents a palindrome of zero or more characters. (The only other palindromes are a, b, c, d, and the empty string.)

Let's try to count palindromes of the form a_a - the other types are similar. Evidently, we should take the first and last a, then count all the palindromes that can be formed in between, as this provides us strictly more possibilities for _ to be a palindrome. This reveals an optimal substructure that is ideal for dynamic programming.

Algorithm

Let dp(i, j) be the number of palindromes (including the palindrome '') in the string T = S[i], S[i+1], ..., S[j]. To count palindromes in T of the form a_a, we will need to know the first and last occurrence of 'a' in this string. This can be done by a precomputed dp: next[i][0] will be the next occurrence of 'a' in S[i:], next[i][1] will be the next occurrence of 'b' in S[i:], and so on.

Also, we will need to know the number of unique letters in T to count the single letter palindromes. We can use the information from next to deduce it: if next[i][0] is in the interval [i, j], then 'a' occurs in T, and so on.

As many states dp(i, j) do not need to be computed, the most natural approach is a top-down variation of dynamic programming.

Complexity Analysis

• Time Complexity: $$O(N^2)$$ , where $$N$$ is the size of the string S. Our calculation of prv and nxt happens in $$O(N)$$ time, then our evaluation of dp with at most $$N^2$$ states is $$O(1)$$ work per state.

• Space Complexity: $$O(N^2)$$ , the size of memo.

Analysis written by: @awice.