LeetCode 647 Palindromic Substrings - Three Solution from O(n³) to O(n) - (Med, Java)

• 647. Palindromic Substrings

When tackling LeetCode 647 (Palindromic Substrings), there are multiple ways to solve the problem. Today, I'll walk through three distinct approaches: the Brute Force method, the Expand Around Centers technique, and the advanced Manacher's Algorithm. Each approach offers different trade-offs between complexity and performance.

Problem Statement

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward.

Example:

• Input: s = "abc"
• Output: 3
• Explanation: Three palindromic strings: "a", "b", "c"

Solution 1: Brute Force - O(n³) Time

The Strategy

The most straightforward approach is to generate all possible substrings and check if each one is a palindrome.

How It Works

1. Generate all substrings: Using nested loops (i to j)
2. Check each substring: Use two pointers to verify if it's a palindrome
3. Count palindromes: Increment counter for each valid palindrome found

class Solution {
    public int countSubstrings(String s){
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++){
            for (int j = i; j < n; j++){
                if (isPalindrome(i, j, s)){
                    count += 1;
                }
            }
        }
        return count;
    }

    private boolean isPalindrome(int i, int j, String s){
        int start = i;
        int end = j;
        while (start <= end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(n³) - O(n²) for generating substrings, O(n) for each palindrome check
• Space Complexity: O(1) - only using a few variables

Pros: Simple and intuitive Cons: Inefficient for large inputs due to cubic time complexity

Solution 2: Expand Around Centers - O(n²) Time

The Strategy

Instead of checking every substring, we expand around potential centers. Every palindrome has a center - either a single character (odd length) or between two characters (even length).

How It Works

1. For each position: Consider it as a potential palindrome center
2. Two types of centers:
   • Odd-length: Center is at position i (e.g., "aba")
   • Even-length: Center is between positions i and i+1 (e.g., "abba")
3. Expand outward: Keep expanding while characters match
4. Count palindromes: Each valid expansion represents a palindrome

public class Solution {
    private int count = 0;

    public int countSubstrings(String s) {
        if (s.length() == 0) {
            return 0;
        }

        for (int i = 0; i < s.length(); i++) {
            // Count odd-length palindromes (center at i)
            help(s, i, i);
            // Count even-length palindromes (center between i and i+1)
            help(s, i, i + 1);
        }
        return count;
    }

    private void help(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
    }
}

Example Walkthrough

For string "aba":

Position 0:

• help(s, 0, 0): "a" ✓ (count = 1)
• help(s, 0, 1): 'a' ≠ 'b' (count = 0)

Position 1:

• help(s, 1, 1): "b" ✓, then "aba" ✓ (count = 2)
• help(s, 1, 2): 'b' ≠ 'a' (count = 0)

Position 2:

• help(s, 2, 2): "a" ✓ (count = 1)

Total: 4 palindromes

Complexity Analysis

• Time Complexity: O(n²) - O(n) positions × O(n) maximum expansion
• Space Complexity: O(1) - only using a few variables

Pros: Efficient, elegant solution Cons: Still quadratic time complexity

Solution 3: Manacher's Algorithm - O(n) Time

The Strategy

Manacher's Algorithm is an advanced technique that can find all palindromes in linear time by preprocessing the string and using previously computed information to avoid redundant checks.

How It Works

1. Preprocessing: Insert '#' between characters to handle odd/even length uniformly

   • "abc" becomes "#a#b#c#"

2. Key Variables:

   • dp[i]: radius of the longest palindrome centered at position i
   • center: center of the rightmost palindrome found so far
   • right: right boundary of the rightmost palindrome

3. Optimization: Use mirror property to avoid redundant computations

   • If i is within a known palindrome, we can use information from its mirror position

4. Expansion: Try to expand the palindrome at each position

5. Counting: Each position contributes (dp[i] + 1) / 2 palindromes to the total count

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        // Preprocess: insert '#' between characters
        StringBuilder t = new StringBuilder("#");
        for (char c : s.toCharArray()) {
            t.append(c).append("#");
        }
        n = t.length();

        int[] dp = new int[n];  // dp[i] = radius of palindrome centered at i
        int center = 0, right = 0;  // rightmost palindrome boundary
        int count = 0;

        for (int i = 0; i < n; i++) {
            int mirror = 2 * center - i;  // mirror of i with respect to center

            // Use previously computed information if within boundary
            if (i < right) {
                dp[i] = Math.min(right - i, dp[mirror]);
            }

            // Attempt to expand palindrome centered at i
            int a = i + (1 + dp[i]);
            int b = i - (1 + dp[i]);
            while (a < n && b >= 0 && t.charAt(a) == t.charAt(b)) {
                dp[i]++;
                a++;
                b--;
            }

            // Update center and right boundary if palindrome expands past right
            if (i + dp[i] > right) {
                center = i;
                right = i + dp[i];
            }

            // Count palindromes: each radius contributes (dp[i] + 1) / 2 palindromes
            count += (dp[i] + 1) / 2;
        }

        return count;
    }
}

Why It Works

The algorithm leverages the symmetry property of palindromes. If we know a palindrome exists from position L to R with center C, then for any position i between C and R, its mirror position j = 2*C - i has already been processed. We can use this information to avoid redundant character comparisons.

Complexity Analysis

• Time Complexity: O(n) - each character is visited at most twice
• Space Complexity: O(n) - for the preprocessed string and dp array

Pros: Optimal linear time complexity Cons: Complex implementation, harder to understand

Performance Comparison

When to Use Each Approach

Use Brute Force when:

• Learning palindrome concepts
• Input size is very small (< 100 characters)
• Code simplicity is prioritized over performance

Use Expand Around Centers when:

• Good balance between simplicity and performance
• Most coding interviews and competitive programming
• Input size is moderate (< 1000 characters)

Use Manacher's Algorithm when:

• Maximum performance is required
• Working with very large inputs (> 10,000 characters)
• Implementing a library function for production use

Key Takeaways

1. Progressive optimization: Start with brute force, then optimize step by step
2. Understand the problem: Palindromes have inherent symmetry that can be exploited
3. Trade-offs matter: Consider implementation complexity vs. performance gains
4. Pattern recognition: Expand around centers is a common technique for palindrome problems
5. Advanced algorithms: Manacher's algorithm shows how mathematical insights can lead to significant optimizations

Each approach has its place depending on your specific requirements. The brute force method is excellent for learning, expand around centers strikes a good balance for most practical applications, and Manacher's algorithm represents the theoretical optimum for this problem.

Understanding all three approaches will make you a more well-rounded developer and help you choose the right tool for the job! 🚀