What We're Solving & Mirror Structures

Finding palindromes within larger string sequences is a classic string analysis challenge frequently featured in technical interviews. The Longest Palindromic Substring problem requires us to locate the longest contiguous block of characters that reads exactly the same both forwards and backwards.

For example, in the string s = "babad", the longest palindromic substring is either "bab" or "aba", both having a length of 3. In s = "cbbd", the longest palindromic substring is "bb" of length 2.

Locating symmetric regions is crucial in several computational domains:

  • Bioinformatics: Used to detect inverted repeats in DNA strands, which indicate protein folding sites and transcription regulations.
  • Data Compression: Identifying recurring mirror sequences allows optimization of dictionary-based compression codecs.
  • Natural Language Processing: Helpful in spell-checking, text segmentation, and semantic structural parsing.

Illustration of Longest Palindromic Substring algorithm expanding around centers in Java
Real-World Analogy: The Reflection Walk

To visualize the expansion strategy, imagine walking down a long pathway lined with letter blocks:

  • Outside-In Checking (Brute Force): To check if a segment is symmetric, you walk to the outer ends and step inward one block at a time, checking if the letters match. If you do this for every possible pair of block combinations, you will be exhausted (this scales quadratically).
  • Inside-Out Checking (The Expansion Walk): Instead, you stand on a single block (or stand in the gap *between* two blocks) and act as a mirror center. You stretch out both arms simultaneously. As long as the letters under your left and right hands are identical, you take a step outward and stretch again.
The moment your hands touch different letters, you stop, record the span distance, and move to the next block center. The largest span you achieve during your walk is the longest palindromic substring.

Solving the Problem

1. The Brute Force Search (O(n³) Complexity)

A naive solution generates every possible substring within the input string and verifies if it is a palindrome. Generating all substrings takes O(n²) iterations, and verifying each palindrome takes O(n) character comparisons. The cumulative O(n³) runtime makes it completely unusable for large datasets.

2. The Expand Around Center Method (O(n²) Time, O(1) Space)

An elegant optimization is to treat every character and space as a potential palindrome center and expand outwards. A string of length n contains exactly 2n - 1 possible centers: n centers on the characters themselves (odd-length palindromes like "aba") and n - 1 centers in the gaps between characters (even-length palindromes like "abba").

For each center, we expand outward using two pointers until a character mismatch occurs or we hit the boundaries. This reduces the runtime to O(n²) while maintaining O(1) space, which is highly efficient.

Detailed Trace Walkthrough

Let's trace the Expand Around Center algorithm step-by-step on the string s = "babad":

  1. Step 1 (Initialization): We set pointers to record our maximum palindrome span: start = 0, end = 0.
  2. Step 2 (Index i = 0, Character 'b'):
    • Odd expansion (centered at 0): Matches 'b'. Out of bounds immediately. Length = 1.
    • Even expansion (centered between 0 and 1): Left is 'b', right is 'a' (mismatch). Length = 0.
    • Max length = 1. Pointers remain: start = 0, end = 0.
  3. Step 3 (Index i = 1, Character 'a'):
    • Odd expansion (centered at 1): Matches 'a'. We step outward: left index 0 ('b') matches right index 2 ('b'). We step outward again: left index -1 is out of bounds. Length = 3 (substring "bab").
    • Even expansion (centered between 1 and 2): Left is 'a', right is 'b' (mismatch). Length = 0.
    • Max length is 3. Since 3 > (end - start + 1), we update pointers: start = 1 - (3 - 1)/2 = 0, end = 1 + 3/2 = 2. Current longest: "bab".
  4. Step 4 (Index i = 2, Character 'b'):
    • Odd expansion (centered at 2): Matches 'b'. Step outward: left index 1 ('a') matches right index 3 ('a'). Substring "aba". Step outward: left index 0 ('b') mismatches right index 4 ('d'). Length = 3.
    • Even expansion (centered between 2 and 3): Mismatch between 'b' and 'a'. Length = 0.
    • Max length is 3. Since 3 is not strictly larger than our current span of 3, the pointers remain: start = 0, end = 2.
  5. Step 5 (Index i = 3, Character 'a'):
    • Odd expansion yields 1. Even expansion yields 0.
  6. Step 6 (Index i = 4, Character 'd'):
    • Odd expansion yields 1. Even expansion yields 0.
  7. Step 7 (Completion):
    • Loop terminates. We extract s.substring(start, end + 1) which maps to s.substring(0, 3), returning "bab" (or "aba" depending on check order).

How the Code Works

The key highlights of our Java implementation:

  • expand(s, i, i) checks for odd palindromes centered at i.
  • expand(s, i, i + 1) checks for even palindromes centered in the gap between i and i + 1.
  • while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) is the expansion condition, stepping outwards (left--, right++) as long as symmetry holds.
  • return right - left - 1 calculates the palindrome length (correcting for the off-by-one mismatch step).

Full Code Solution

Below is the complete Java implementation featuring both the brute-force search and the optimized O(n²) Expand Around Center algorithm, along with a main runner method.

package io.practise.dsa;
 
public class LongestPalindromicSubstring {
 
    // Brute Force - O(n^3)
    public String longestPalindromeBrute(String s) {
        int maxLen = 0;
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (isPalindrome(sub) && sub.length() > maxLen) {
                    result = sub;
                    maxLen = sub.length();
                }
            }
        }
        return result;
    }
 
    private boolean isPalindrome(String str) {
        int l = 0, r = str.length() - 1;
        while (l < r) {
            if (str.charAt(l++) != str.charAt(r--)) return false;
        }
        return true;
    }
 
    // Optimized - O(n^2) Expand Around Center
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i); // Odd length
            int len2 = expand(s, i, i + 1); // Even length
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
 
    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
 
    public static void main(String[] args) {
        LongestPalindromicSubstring solver = new LongestPalindromicSubstring();
        String s = "babad";
 
        System.out.println("--- Longest Palindromic Substring Demonstration ---");
        System.out.println("Input String: " + s);
 
        String result = solver.longestPalindrome(s);
        System.out.println("Longest Palindrome: " + result);
    }
}

Conclusion & Takeaways

Solving the Longest Palindromic Substring problem highlights how we can optimize string processing by changing the direction of comparisons. Expanding outward from potential centers rather than scanning substrings from the outside inward reduces comparison redundancy and achieves a highly optimized solution.