In the realm of programming, strings are a foundational data structure. Among various string-related problems, counting palindromic substrings frequently turns up in coding interviews and competitive programming contests. A palindromic substring is a sequence of characters that reads the same forward and backward (like "racecar" or "level"). This blog dives into mastering the techniques to efficiently count palindromic substrings in a given string.

Understanding Palindromic Substrings

Before we jump into the methods, let’s clarify what a palindromic substring is. Given an example string:

Input: "abba"

The palindromic substrings here are:

• "a"
• "b"
• "b"
• "a"
• "abba"
• "bb"

This string contains a total of 6 palindromic substrings.

Naive Approach

The simplest method to find palindromic substrings involves checking every substring of the given string. Here's how you might approach that:

1. Iterate over all possible substrings using two loops.
2. For each substring, check if it is a palindrome.

Implementation

def is_palindrome(s):
    return s == s[::-1]

def palindromic_substrings_count(s):
    count = 0
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n + 1):
            if is_palindrome(s[i:j]):
                count += 1
    return count

# Example usage
print(palindromic_substrings_count("abba"))  # Output: 6

Complexity

The time complexity for this approach is O(n^3) due to:

• Generating all substrings in O(n^2).
• Checking if each substring is a palindrome in O(n).

This method works, but it’s not optimal for large strings.

Optimized Approach: Expand Around Center

To optimize our method, we can leverage the technique of expanding around possible centers for palindromic substrings. Each palindrome can be expanded from its center, accounting for both odd and even-length palindromes.

Steps to implement:

1. Iterate through each index of the string.
2. For each index, expand outward to check for palindromes.
3. Consider two scenarios for each character:
   • Expand around the character for odd-length palindromes.
   • Expand around the gap between two characters for even-length palindromes.

Implementation

def count_palindromic_substrings(s):
    def expand_around_center(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count

    total_count = 0
    for i in range(len(s)):
        # Odd-length palindromes
        total_count += expand_around_center(i, i)
        # Even-length palindromes
        total_count += expand_around_center(i, i + 1)

    return total_count

# Example usage
print(count_palindromic_substrings("abba"))  # Output: 6

Complexity

This optimized method has a time complexity of O(n^2), making it efficient enough for moderate-sized strings. The space complexity is O(1), as it uses only a constant amount of space.

Applying Dynamic Programming

An even more efficient approach, particularly useful in some contexts, is using dynamic programming (DP). This method involves storing previously computed results to avoid redundant calculations.

Steps for Dynamic Programming:

1. Create a 2D array (table) to keep track of palindromic substrings.
2. Iterate through possible substrings, filling the table based on the characters and previously calculated results.
3. Count the palindromic substrings based on table entries.

Implementation

def count_palindromic_substrings_dp(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0

    for length in range(1, n + 1):  # Lengths from 1 to n
        for start in range(n - length + 1):
            end = start + length - 1
            if s[start] == s[end]:
                if length <= 2:  # Two same chars or single char
                    dp[start][end] = True
                else:  # More than 2 chars
                    dp[start][end] = dp[start + 1][end - 1]

                if dp[start][end]:
                    count += 1

    return count

# Example usage
print(count_palindromic_substrings_dp("abba"))  # Output: 6

Complexity

The DP approach has a time complexity of O(n^2) and a space complexity of O(n^2) due to the table storage, which works well for strings subjected to length limitations.

Conclusion

By delving into different methods to count palindromic substrings, you can elevate your string manipulation skills and prepare yourself for technical interviews. You can explore basic approaches like brute force, optimized expanding methods, and dynamic programming techniques tailored for palindromic patterns.

Now that you have several techniques in your arsenal, practice applying these methods to various string problems, and watch your problem-solving skills soar!