Introduction to Palindromic Substrings

A substring is a contiguous sequence of characters within a string. A palindrome is a string that reads the same forward and backward, such as "radar" or "level". The challenge of finding palindromic substrings in a given string is a common problem in coding interviews and can be approached with various algorithms, especially using dynamic programming.

In this post, we will dissect this problem into manageable parts, showcasing how you can implement an effective solution.

Understanding the Problem

Let's consider the string s = "abba". The palindromic substrings present in this string include:

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

Thus, our goal is to identify and count these unique palindromic substrings.

Brute Force Approach

The simplest way to tackle the problem is through a brute-force method. Here's how it works:

1. Generate all possible substrings of the given string.
2. For each substring, check if it is a palindrome.
3. Maintain a count of unique palindromic substrings.

Example Implementation

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

def count_palindromic_substrings_brute(s):
    count = 0
    unique_palindromes = set()
    n = len(s)
    
    for i in range(n):
        for j in range(i, n):
            substr = s[i:j+1]
            if is_palindrome(substr):
                unique_palindromes.add(substr)
                
    return len(unique_palindromes)

# Test
s = "abba"
print(count_palindromic_substrings_brute(s))  # Output: 6

While this method is straightforward, its time complexity is O(n^3) due to the nested loops and palindrome checking, making it inefficient for longer strings.

Dynamic Programming Approach

Dynamic programming can significantly optimize our approach. The idea is to use a 2D table that keeps track of whether a substring s[i:j] is a palindrome.

Step-by-Step Approach

1. Create a 2D array dp of size n x n, where dp[i][j] will be True if the substring s[i:j] is a palindrome.
2. Initialize the diagonals (i.e., single characters) as True since every single character is a palindrome.
3. Check for two-character palindromes and fill the table accordingly.
4. For substrings longer than two characters, the substring s[i:j] is a palindrome if s[i] == s[j] and dp[i+1][j-1] is True.
5. Count palindromic substrings as you fill the DP table.

Example Implementation

def count_palindromic_substrings_dp(s):
    n = len(s)
    if n == 0:
        return 0

    dp = [[False] * n for _ in range(n)]
    count = 0

    for i in range(n):
        dp[i][i] = True  # Single character palindromes
        count += 1

    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1

    for length in range(3, n + 1):  # Check for substrings of length >= 3
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1

    return count

# Test
s = "abba"
print(count_palindromic_substrings_dp(s))  # Output: 6

Time Complexity

The time complexity of the dynamic programming approach is O(n^2), and the space complexity is also O(n^2) due to the extra space used for the DP table.

Expansion Around Center Method

Another efficient approach involves treating each character and each pair of characters as potential centers of a palindrome. We expand outwards from these centers while the characters are equal.

Example Implementation

def count_palindromic_substrings_center(s):
    n = len(s)
    if n == 0:
        return 0

    count = 0

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

    for i in range(n):
        expand_around_center(i, i)    # Odd length palindromes
        expand_around_center(i, i + 1)  # Even length palindromes

    return count

# Test
s = "abba"
print(count_palindromic_substrings_center(s))  # Output: 6

Time Complexity

This method has a time complexity of O(n^2) and space complexity of O(1), making it very efficient in terms of space.

Summary of Techniques

1. Brute Force: Simple but inefficient with O(n^3) complexity.
2. Dynamic Programming: More efficient, O(n^2) time and space complexity, fills a table for palindrome detection.
3. Expansion Around Center: Another O(n^2) method, optimized for space with O(1) usage, great for interview scenarios.

By applying these techniques, one can efficiently solve the problem of counting palindromic substrings and enhance dynamic programming skills within data structures and algorithms.