DP - Palindromic Substrings

Given a string s, return the number of palindromic substrings in it.

A string is palindromic if it reads the same forward and backward. For example abcba is a palindromic string that expands from center letter c and abba is also a palindromic string that expands with no center letter.

Input: s = "abc"
Output: 3
Explanation: there are three palindromic substrings in the input string "a", "b" and "c".

Input: s = "aaa"
Output: 6
Explanation: there are six palindromic substrings "a", "a", "a", "aa", "aa" and "aaa".

This problem is similar to Longest palindrome substring and the only difference in current problem is that we are finding all palindromic substrings and returning that count as result. So, we are going to discuss the optimized solution that we have seen in longest palindromic substring problem, which is expand around center.

Solution - expand around center

In this approach, what we are going to do is, from every index in the string, we try to expand to the left and to the right and check whether the characters on both sides are same or not.

Create a helper method expandAroundCenterHelper that takes parameters input string s, int l and int r left and right indexes to expand around and count number of palindromes found from that index.
- In the implementation of this method, create a variable total to keep track of all palindromes found.
- We will then try to expand the palindromic substring using left and right indexes l and r.
- While l and r within the boundararies of input string's length, check character at l^th index and r^th indexes are same, that means we have found a palindrome, then increment total count, decrement l and increment r and continue.
Now, call the helper method created above for both odd length palindromes and even length palindromes, by supplying left and right indexes as i, i for odd length palindromes, then i, i+1 for even length palindromes. Then, keep track of total palindromes found, both odd length palindromes and even length palindromes.

l= i; r= i;

l= i; r= i+1;

For example, when you expand around center for input string "babad", it will produce below output as 7.
If you see the input string, every single character is a palindrome on its own, they are 'b', 'a', 'b', 'a' and 'd', then there are two other odd length palindromes 'bab' and 'aba' and there are no even length palindromes in the input string.

public class PalindromicSubstrings { static int expandAroundCenter(String s) { int total = 0; for (int i=0; i<s.length(); i++) { int oddLengthPalindromes = expandAroundCenterHelper(s, i, i); int evenLengthPalindromes = expandAroundCenterHelper(s, i, i+1); total += oddLengthPalindromes + evenLengthPalindromes; } return total; } static int expandAroundCenterHelper(String s, int l, int r) { int total = 0; while(l>=0 && r<s.length() && s.charAt(l) == s.charAt(r)) { total++; l--; r++; } return total; } }

Complexity Analysis:

Time complexity: Above code runs in O(n²) time where n is the length of the input string. For every index in the string, we are expanding to the left and right side.
Space complexity: O(1), since we are keep tracking of total count only.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis: