647. Palindromic Substrings

Problem Description

The problem requires us to determine the number of palindromic substrings in a given string s. A palindromic substring is defined as a substring that reads the same backward as forward. Substrings are contiguous sequences of characters that are formed from the string. For example, in the string "abc", "a", "b", "c", "ab", "bc", and "abc" are all substrings. The solution to the problem should count all such substrings that are palindromes.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The intuition behind the solution lies in recognizing that a palindromic substring can be centered around either a single character or a pair of identical characters. With this understanding, we can extend outwards from each possible center and check for palindrome properties.

The solution uses an algorithm known as "Manacher's Algorithm", which is efficient for finding palindromic substrings. The key idea is to avoid redundant computations by storing and reusing information about previously identified palindromes.

Steps underlying Manacher's algorithm:

Transform the String: Insert a dummy character (say #) between each pair of characters in the original string (and at the beginning and end). This transformation helps us handle even-length palindromes uniformly with odd-length palindromes. The insertion of '^' at the beginning and '$' at the end prevents index out-of-bound errors.
Array Initialization: Create an array p that will hold the lengths of the palindromes centered at each character of the transformed string.
Main Loop: Iterate through each character of the transformed string, treating it as the center of potential palindromes. For each center, expand outwards as long as the substring is a palindrome.
Center and Right Boundary: Keep track of the rightmost boundary (maxRight) of any palindrome we've found and the center of that palindrome (pos). This is used to optimize the algorithm by reusing computations for palindromes that overlap with this rightmost palindrome.
Update and count: During each iteration, update the p array with the new palindrome radius and calculate the number of unique palindromes up to that point. Due to the transformation of the string, divide the radius by 2 to get the count of actual palindromes in the original string.
Result: The sum of the values in p divided by 2 gives us the total count of palindromic substrings in the original string.

The efficiency of Manacher's algorithm comes from the fact that it cleverly reuses previously computed palindromic lengths and thus avoids re-computing the length of a palindrome when each new centered palindrome is considered. It runs in linear time relative to the length of the transformed string, making it much more efficient than a naive approach.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of the solution using Manacher's algorithm follows the underlying steps:

String Transformation: The given string s is first transformed into t by inserting '#' between each character and adding a beginning marker '^' and an end marker '$'. This transformation ensures that we consider both even and odd-length palindromes by making every palindrome center around a character in t.
Initialize Variables: Three main variables are initiated:
- pos: The center of the palindrome that reaches furthest to the right.
- maxRight: The right boundary of this palindrome.
- ans: The total count of palindromic substrings (to be computed).
Array p for Palindrome Radii: An array p is created with the same length as the transformed string t. Each element p[i] will keep track of the maximum half-length of the palindrome centered at t[i].
Iterate Over t: We iterate over each character in the transformed string (excluding the first and last characters which are the markers), checking for palindromic substrings.
Calculate Current Palindrome Radius:
- If the current index i is within the bounds of a known palindrome, we initialize p[i] to the minimum of maxRight - i and the mirror palindrome length, p[2 * pos - i].
- If i is beyond maxRight, we start with a potential palindrome radius of 1.
Expand Around Centers:
- We expand around the current center i by incrementing p[i] as long as characters at i + p[i] and i - p[i] are equal (palindromic condition).
- This loop helps in finding the maximum palindrome centered at i.
Update Right Boundary and Center (pos):
- If the current palindrome goes past the maxRight, update maxRight and pos to the new values based on the current center i and its palindrome radius p[i].
Counting Substrings:
- The palindrome length for the center i divided by 2 is added to ans. This accounts for the fact that only half the length of palindromes in the transformed string is relevant due to the inserted characters ('#').
Return Result: Finally, the variable ans holds the total count of palindromic substrings in the original string, which is then returned.

In summary, the solution effectively leverages Manacher's algorithm for the palindrome counting problem. It transforms the input string to facilitate the uniform handling of even and odd length palindromes, utilizes dynamic programming through array p to store palindrome lengths, and optimizes by remembering the furthest reaching palindrome to avoid redundant checks.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the string s = "abba".

String Transformation: Inserting '#' between each character of s and adding '^' at the beginning and '$' at the end, the transformed string t becomes: ^#a#b#b#a#$.
Initialize Variables:
- pos is set to 0.
- maxRight is set to 0.
- ans is initialized as 0, which will hold the count of palindromic substrings.
Array p for Palindrome Radii: We create an array p with length equal to t, which is 11. Initially, p is filled with zeros: p = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
Iterate Over t: We ignore the first and last characters (^ and $) and start iterating from the second character (index 1) to the second to last (index 9).
Calculate Current Palindrome Radius:
- For the first character # after ^, since maxRight is 0, we start with p[1] = 1.
- Next, we examine a. Since maxRight is still 0, we also start p[2] = 1.
Expand Around Centers:
- The palindrome at the second character # can't be expanded, so p[1] remains 1.
- For a at index 2, we can expand one step outward to check the characters around it (# on both sides), and it's still a palindrome. So p[2] = 2.
Update Right Boundary and Center (pos):
- For a at index 2, since i + p[i] (2 + 2) is greater than maxRight (0), we update:
  - maxRight = 4
  - pos = 2.
Counting Substrings:
- After updating maxRight and pos for a, we add p[2] / 2 to ans, which means we add 1 to ans.
- Proceeding with the same logic, for # at index 3 and b at index 4, we'll find that they form a longer palindrome of length 4 (since b#b#b is a palindrome). So p[3] = 2, and p[4] = 4, and our ans will be updated accordingly.
Return Result: Continuing this process for all characters in t and summing up p[i] / 2 for each character, we get the total count of palindromic substrings in the original string s as ans.

For s = "abba", the final result is 6 which represents the palindromic substrings: a, b, b, a, bb, and abba.

Solution Implementation

1class Solution:
2    def countSubstrings(self, s: str) -> int:
3        # Preprocess the string to insert '#' between characters and '^', '$' at the ends.
4        # This helps to handle palindrome of even length properly.
5        transformed_string = '^#' + '#'.join(s) + '#$'
6        n = len(transformed_string)
7
8        # Array to store the length of the palindrome centered at each character in T.
9        palindrome_lengths = [0] * n
10
11        # Current center, and the right boundary of the rightmost palindrome.
12        center, right_boundary = 0, 0
13
14        # Accumulator for the count of palindromic substrings.
15        palindromic_substring_count = 0
16
17        # Loop through the transformed string starting from the first character after '^'
18        # and ending at the last character before '$'.
19        for i in range(1, n - 1):
20            # If the current position is within the rightmost palindrome, we can use
21            # previously calculated data (palindrome_lengths[2 * center - i])
22            # to determine the minimum length for the palindrome centered at i.
23            if right_boundary > i:
24                palindrome_lengths[i] = min(right_boundary - i, palindrome_lengths[2 * center - i])
25            else:
26                palindrome_lengths[i] = 1  # Start with a palindrome of length 1 (a single character).
27
28            # Expand around the center i, and check for palindromes.
29            while transformed_string[i + palindrome_lengths[i]] == transformed_string[i - palindrome_lengths[i]]:
30                palindrome_lengths[i] += 1
31
32            # Update the rightmost palindrome's boundary and center position
33            # if the palindrome centered at i expands past it.
34            if i + palindrome_lengths[i] > right_boundary:
35                right_boundary = i + palindrome_lengths[i]
36                center = i
37
38            # Increment the count of palindromic substrings.
39            # We divide by 2 because we inserted '#' and need the actual length.
40            palindromic_substring_count += palindrome_lengths[i] // 2
41
42        return palindromic_substring_count
43

1class Solution {
2    public int countSubstrings(String s) {
3        // Initialize a StringBuilder to hold the transformed string with boundary characters
4        StringBuilder transformedString = new StringBuilder("^#");
5        // Transform the input string by inserting '#' between characters
6        // This is done to handle both even and odd length palindrome uniformly
7        for (char ch : s.toCharArray()) {
8            transformedString.append(ch).append('#');
9        }
10        // Finalize the transformed string by adding a '$' at the end
11        // This prevents index out of range during the while loop checks
12        transformedString.append('$');
13        String modifiedStr = transformedString.toString();
14
15        int length = modifiedStr.length();
16        // Array to hold the length of the palindrome at each index
17        int[] palindromeLengths = new int[length];
18
19        // Initialize center and right boundary of the current longest palindrome
20        int center = 0;
21        int rightBoundary = 0;
22        // Variable to store the total count of palindromes
23        int countPalindromes = 0;
24
25        // Loop through the string starting from the first character index to the second last
26        for (int i = 1; i < length - 1; i++) {
27            // Determine the mirror index of the current index `i`
28            int mirror = 2 * center - i;
29
30            // Check if the current right boundary exceeds the current index
31            // If so, pick the minimum between the mirrored palindrome's length and the distance to the right boundary
32            palindromeLengths[i] = rightBoundary > i ? Math.min(rightBoundary - i, palindromeLengths[mirror]) : 1;
33
34            // Expand around the center to determine the length of palindrome at index `i`
35            while (modifiedStr.charAt(i - palindromeLengths[i]) == modifiedStr.charAt(i + palindromeLengths[i])) {
36                palindromeLengths[i]++;
37            }
38
39            // If the palindrome expanded past the right boundary, update the center and right boundary
40            if (i + palindromeLengths[i] > rightBoundary) {
41                rightBoundary = i + palindromeLengths[i];
42                center = i;
43            }
44
45            // Increment countPalindromes by half the length of palindromes at i (since we insert #'s)
46            // This will effectively count each character in the original string once
47            countPalindromes += palindromeLengths[i] / 2;
48        }
49
50        // Return the total count of palindromic substrings
51        return countPalindromes;
52    }
53}
54

1class Solution {
2public:
3    int countSubstrings(string s) {
4        int totalCount = 0; // Initialize count of palindromic substrings
5        int length = s.size(); // Get the size of the input string
6
7        // Iterate over the string, considering both odd and even length palindromes
8        for (int center = 0; center < length * 2 - 1; ++center) {
9            // For an odd-length palindrome, both i and j start at the same index.
10            // For an even-length palindrome, j starts at the next index after i.
11            int left = center / 2;
12            int right = (center + 1) / 2;
13
14            // Expand around the center as long as the characters are the same
15            while (left >= 0 && right < length && s[left] == s[right]) {
16                ++totalCount; // Increment the count for the current palindrome
17                --left;  // Move the left pointer backward
18                ++right; // Move the right pointer forward
19            }
20        }
21        return totalCount; // Return the total count of palindromic substrings
22    }
23};
24

1/**
2 * Counts the number of palindromic substrings in a given string.
3 *
4 * @param {string} str - The string to analyze.
5 * @return {number} - The count of palindromic substrings.
6 */
7function countSubstrings(str: string): number {
8    let count: number = 0;
9    const length: number = str.length;
10
11    // Iterate through each character position in the string, expanding potential palindromes.
12    for (let center = 0; center < length * 2 - 1; ++center) {
13        // Find the starting positions of potential palindromes.
14        let left: number = center >> 1;
15        let right: number = (center + 1) >> 1;
16
17        // Expand around the center while the characters match and we're within the bounds of the string.
18        while (left >= 0 && right < length && str[left] == str[right]) {
19            // Increment the palindrome count.
20            ++count;
21            // Move outwards to check the next characters.
22            --left;
23            ++right;
24        }
25    }
26    return count;
27}
28

Time and Space Complexity

The given code implements the Manacher's algorithm for finding the total number of palindrome substrings in a given string s.

The time complexity of the Manacher's algorithm is O(n), where n is the length of the transformed string t. The transformation involves adding separators and boundaries to the original string, effectively doubling its length and adding two extra characters; thus, the length of t is roughly 2 * len(s) + 3. The main loop of the algorithm iterates through each character of the transformed string t once, and the inner while loop that checks for palindromes does not increase the overall time complexity since the expansion of p[i] can only be as large as the length of t.

As for the space complexity, the algorithm allocates an array p that is the same length as t, so the space complexity is also O(n), where n is the length of the transformed string t.

Therefore, when we relate it back to the original string s, the time and space complexities can be considered O(n) as well, with n = len(s).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

A graph is a special tree

A tree is a special graph

No relationship

They are the same thing

I don't know