Expand Around Possible Centers

Back at it again with another algorithm blog! Today we will talk about one of the popular questions in Leetcode, #647 Palindromic Substrings. There are many ways to solve this problem. We are going to talk about ‘ expand around possible centers here.

Here is the question:

Leetcode #647 Palindromic Substrings

We want to return the number of ways to obtain a non-empty palindrome by trimming the string’s left and right sides (but without rearranging the string). As long as it produces a palindrome, the left and right trims can also be empty.

Intuition: Expand Around Possible Centers

The intuition of ‘expand around possible centers’ is that palindromes are like onions, you remove the boundary characters, and you are left with another, a smaller palindrome. Palindromes have the same centers; with those centers, we can expand around them, and from there, we can find substring palindromes as long as we can make larger and larger palindromes. For instance: let’s take the string ‘never’ if we choose ‘v’ as the center ‘v’ and ‘eve’ are palindrome. But the final expansion ‘never’ is not a palindrome since the first and last characters are not matched.

Algorithm solution

They are two steps with the ‘expand around possible centers’ algorithm.

• First: We will need to find all possible centers for potential palindromes. With this in mind, there are two cases: we see every single character in the string is a center for possible odd-length and even-length palindromes. ( example 1, we can solve it with odd length palindromes, on the other hand, in example 2, we need both odd and even length palindromes to get the total palindrome substring)
• Second: For every center we find, we can expand it as long as we get palindromes(the first and last characters should match).

Solution: Expand Around Possible Centers

Time and Space Complexity

There are better approaches to solving the problem more efficiently. However, those are significantly complex and impractical to implement in interviews. “Expand Around Possible Centers” is a good enough practice approach for interviews. The time complexity is O(n²), and the space complexity is O(1).

So there you go, that is the concept of “Expand Around PossibleCenters”! Thanks for reading, and I hope you enjoy it!