Brute Force Approach - Longest Palindromic Substring | OneNoughtOne

0/361

Data Structures & AlgorithmsLongest Palindromic Substring

Longest Palindromic Substring

LevelIntermediate

Duration75 mins

TopicLongest Palindromic Substring

1 / 4

Brute Force Approach

The Longest Palindromic Substring Problem

Palindromes—strings that read the same forwards and backwards—have fascinated mathematicians, linguists, and computer scientists alike. From the simple "racecar" to the legendary "A man, a plan, a canal: Panama," palindromes appear throughout language and culture. But beyond their linguistic charm, finding palindromic substrings efficiently is a fundamental algorithmic challenge with significant practical applications.

The Longest Palindromic Substring (LPS) problem asks: Given a string S, find the longest contiguous substring of S that is a palindrome. This seemingly simple question opens a fascinating exploration of algorithmic design, from naive approaches to elegant linear-time solutions.

Consider the string "babad". What is its longest palindromic substring? The answer could be "bab" or "aba"—both are valid since they share the same length (3). For "cbbd", the answer is "bb". For "racecar", the entire string is the answer.

What You Will Learn

By the end of this page, you will understand the naive brute force approach to finding the longest palindromic substring. You'll learn to systematically enumerate all substrings, verify palindromes, and track the maximum. Most importantly, you'll understand why this O(n³) approach, while correct, motivates the search for more efficient algorithms.

Understanding Palindromes Formally

Before diving into algorithms, let's establish a precise, mathematical understanding of palindromes and the problem we're solving.

Definition: Palindrome

A string S of length n is a palindrome if and only if:

S[i] = S[n - 1 - i] for all i where 0 ≤ i < n

In other words, the character at position i from the start equals the character at position i from the end. This definition applies to both even-length and odd-length strings:

Odd-length palindrome: Has a single center character (e.g., "aba" with center 'b')
Even-length palindrome: Has two center characters (e.g., "abba" with center 'bb')

Every single character is trivially a palindrome of length 1. The empty string is also considered a palindrome by convention.

Palindrome Verification Examples
String	Length	Type	Is Palindrome?	Reason
"a"	1	Odd	✓ Yes	Single character
"aa"	2	Even	✓ Yes	S[0]='a' = S[1]='a'
"ab"	2	Even	✗ No	S[0]='a' ≠ S[1]='b'
"aba"	3	Odd	✓ Yes	S[0]='a' = S[2]='a', center 'b' matches itself
"abba"	4	Even	✓ Yes	S[0]='a' = S[3]='a', S[1]='b' = S[2]='b'
"abcba"	5	Odd	✓ Yes	Symmetric around center 'c'
"abcca"	5	Odd	✗ No	S[0]='a' = S[4]='a', but S[1]='b' ≠ S[3]='c'

Substring vs Subsequence

The problem asks for the longest palindromic substring—a contiguous sequence of characters. This is different from the longest palindromic subsequence problem, which allows non-contiguous characters. For "character", the longest palindromic substring is "ara" or "rac" (length 3), but the longest palindromic subsequence is "carac" (length 5). Substring problems are typically O(n²) or better; subsequence problems often require O(n²) dynamic programming.

The Problem Statement, Precisely

Given a string S of length n over some alphabet Σ:

Input: String S = s₀s₁s₂...sₙ₋₁

Output: A substring S[i...j] (where 0 ≤ i ≤ j < n) such that:

S[i...j] is a palindrome
The length (j - i + 1) is maximized

If multiple substrings of the same maximum length exist, any one may be returned.

Key observations:

There are O(n²) possible substrings (each pair of start and end indices)
Checking if a string is a palindrome naively takes O(n) time
This immediately suggests an O(n³) brute force approach

The Brute Force Strategy

The brute force approach follows the most straightforward reasoning: enumerate every possible substring, check if it's a palindrome, and keep track of the longest one found.

This approach requires no clever insights—just systematic enumeration. While computationally expensive, it's valuable for several reasons:

Correctness verification: It provides a reference implementation to test optimized algorithms
Understanding the problem space: Seeing all O(n²) substrings clarifies what we're searching through
Baseline complexity: Establishes the performance bar that better algorithms must beat
Interview foundation: Demonstrating the brute force first shows clear thinking progression

Brute Force Algorithm Steps

•Initialize tracking variables: Store the starting index and maximum length of the longest palindrome found so far. Initialize to the first character (guaranteed palindrome of length 1).
•Enumerate all starting positions: Loop through each index i from 0 to n-1 as potential substring starts.
•Enumerate all ending positions: For each start i, loop through each index j from i to n-1 as potential substring ends.
•Check palindrome property: For each substring S[i...j], verify if it's a palindrome by comparing characters from both ends moving inward.
•Update maximum: If the substring is a palindrome and its length exceeds the current maximum, update the tracking variables.
•Return result: After checking all substrings, extract and return the longest palindromic substring using the stored indices.

Visualizing the Enumeration

For a string of length 5 like "babad", the brute force algorithm examines the following substrings:

Length 1: "b", "a", "b", "a", "d" (5 substrings)
Length 2: "ba", "ab", "ba", "ad" (4 substrings)
Length 3: "bab", "aba", "bad" (3 substrings)
Length 4: "baba", "abad" (2 substrings)
Length 5: "babad" (1 substring)

Total: 5 + 4 + 3 + 2 + 1 = 15 substrings = n(n+1)/2 substrings in general.

For each substring, we then check if it's a palindrome, which requires comparing up to half its characters.

The Palindrome Verification Function

At the heart of the brute force approach is a helper function that determines whether a given substring is a palindrome. This function is called O(n²) times, so its efficiency matters.

The Two-Pointer Technique

The classic palindrome verification uses two pointers:

Left pointer starts at the beginning of the substring
Right pointer starts at the end of the substring
Move inward, comparing characters at each step
If any mismatch occurs, the string is not a palindrome
If pointers meet or cross without mismatch, it's a palindrome

This check runs in O(k) time for a substring of length k, giving O(n) worst-case per call.

palindrome_check.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def is_palindrome(s: str, left: int, right: int) -> bool:
    """
    Check if s[left:right+1] is a palindrome.
    
    Args:
        s: The original string
        left: Starting index (inclusive)
        right: Ending index (inclusive)
    
    Returns:
        True if the substring is a palindrome, False otherwise
    
    Time Complexity: O(right - left + 1) = O(n) worst case
    Space Complexity: O(1)
    """
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
 
 
# Example usage
text = "racecar"
 
# Check various substrings
print(is_palindrome(text, 0, 6))  # True: "racecar"
print(is_palindrome(text, 0, 3))  # False: "race"
print(is_palindrome(text, 1, 5))  # True: "aceca"
print(is_palindrome(text, 2, 4))  # True: "cec"

Why Pass Indices Instead of Creating Substrings?

Notice that we pass the indices (left, right) rather than creating a new substring. This is a crucial optimization! Creating a substring in most languages requires O(k) time and O(k) space to copy k characters. By working with indices, our verification remains O(k) time but uses O(1) space. This seemingly minor detail impacts real-world performance significantly.

The Complete Brute Force Implementation

Now let's combine everything into a complete, production-quality brute force solution. We'll implement the full algorithm with careful attention to edge cases and clarity.

brute_force_lps.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
def longest_palindromic_substring_brute_force(s: str) -> str:
    """
    Find the longest palindromic substring using brute force.
    
    Algorithm:
    1. Enumerate all O(n²) substrings
    2. Check each for palindrome property
    3. Track the longest palindrome found
    
    Args:
        s: Input string
    
    Returns:
        The longest palindromic substring
    
    Time Complexity: O(n³)
        - O(n²) substrings to enumerate
        - O(n) to check each substring for palindrome property
    
    Space Complexity: O(1)
        - Only storing indices, not creating new strings during search
        - Final substring creation is O(n) but that's for the output
    """
    if not s:
        return ""
    
    n = len(s)
    
    # Track the best palindrome found
    # Start with the first character (always a valid palindrome)
    best_start = 0
    best_length = 1
    
    def is_palindrome(left: int, right: int) -> bool:
        """Check if s[left:right+1] is a palindrome."""
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    
    # Enumerate all substrings
    for i in range(n):
        for j in range(i, n):
            length = j - i + 1
            
            # Optimization: only check if longer than current best
            if length > best_length and is_palindrome(i, j):
                best_start = i
                best_length = length
    
    return s[best_start:best_start + best_length]
 
 
# Comprehensive test cases
test_cases = [
    ("babad", ["bab", "aba"]),      # Two valid answers
    ("cbbd", ["bb"]),                # Even-length palindrome
    ("a", ["a"]),                    # Single character
    ("ac", ["a", "c"]),              # No palindrome > 1
    ("racecar", ["racecar"]),        # Entire string
    ("", [""]),                      # Empty string
    ("aaaa", ["aaaa"]),              # All same characters
    ("abcba", ["abcba"]),            # Odd-length palindrome
    ("abaaba", ["abaaba"]),          # Full string is palindrome
    ("forgeeksskeegfor", ["geeksskeeg"]),  # Long example
]
 
print("Brute Force LPS Testing")
print("=" * 50)
 
for s, expected in test_cases:
    result = longest_palindromic_substring_brute_force(s)
    status = "✓" if result in expected else "✗"
    print(f"{status} Input: "{s}"")
    print(f"  Result: "{result}" (Length: {len(result)})")
    print()

Rigorous Complexity Analysis

Understanding the complexity of the brute force approach is essential for appreciating why we need better algorithms. Let's analyze both time and space complexity rigorously.

Time Complexity: O(n³)

The algorithm has three nested operations:

Outer loop over starting index i: runs n times
Inner loop over ending index j: runs up to n - i times
Palindrome check for substring s[i...j]: runs up to j - i + 1 times

Let's compute the exact number of operations:

Detailed Count of Operations

For each pair (i, j), we perform O(j - i + 1) comparisons. The total number of comparisons is:

$$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1} (j - i + 1)$$

Let's substitute k = j - i (the length minus 1):

$$\sum_{i=0}^{n-1} \sum_{k=0}^{n-1-i} (k + 1) = \sum_{i=0}^{n-1} \sum_{k=1}^{n-i} k$$

Using the formula for sum of first m integers: $\sum_{k=1}^{m} k = \frac{m(m+1)}{2}$:

$$\sum_{i=0}^{n-1} \frac{(n-i)(n-i+1)}{2}$$

This evaluates to approximately $\frac{n^3}{6}$, confirming O(n³) complexity.

For a string of length 1000, this means roughly 166 million comparisons. For length 10,000, it's 166 billion comparisons—clearly impractical.

Brute Force Performance at Different Scales
String Length (n)	Substrings O(n²)	Operations O(n³)	Estimated Time*
100	5,050	~170,000	< 1 ms
1,000	500,500	~166,000,000	~100 ms
10,000	50,005,000	~166,000,000,000	~100 seconds
100,000	5,000,050,000	~166 trillion	~28 hours
1,000,000	500 billion	~166 quadrillion	~3 years

The Cubic Curse

The O(n³) complexity makes brute force impractical for strings longer than a few thousand characters. Most competitive programming problems and real-world applications involve strings of 10⁴ to 10⁶ characters, where brute force would time out or run for days. This stark limitation drives the need for the O(n²) and O(n) algorithms we'll explore in subsequent pages.

Space Complexity: O(1)

The brute force algorithm uses constant extra space:

Two variables for tracking indices of the best palindrome found
Two pointers for the palindrome check
No auxiliary data structures proportional to input size

The final output string requires O(n) space in the worst case (when the entire string is a palindrome), but this is typically not counted against the algorithm's space complexity since it's the required output.

Summary:

Time: O(n³) — too slow for large inputs
Space: O(1) — optimal auxiliary space

Why Brute Force Matters Despite Its Inefficiency

Given its O(n³) complexity, why study the brute force approach at all? This naive algorithm serves several critical purposes in algorithm design and software engineering practice.

The Value of Brute Force Solutions

•Correctness Baseline — The brute force solution is trivially correct. It exhaustively checks every possibility, leaving no edge cases unexplored. This makes it an invaluable reference for testing optimized solutions against.
•Problem Understanding — Implementing brute force forces you to understand the problem completely. What constitutes a valid substring? How do we define palindrome? What are the edge cases? You can't optimize what you don't understand.
•Interview Communication — In technical interviews, starting with brute force demonstrates systematic thinking. It shows you can solve the problem before you optimize, and provides a foundation for discussing improvements.
•Small Input Practicality — For strings under ~500 characters, brute force runs in acceptable time. Many real-world scenarios have bounded input sizes where the simplicity of brute force outweighs its theoretical inefficiency.
•Test Generation — Brute force implementations are perfect for generating expected outputs in test suites. Their simplicity minimizes bugs, providing reliable ground truth for validating complex optimizations.

The Optimization Journey

Great algorithm designers don't jump to optimal solutions. They start with correctness, then optimize systematically. Donald Knuth's famous advice: "Premature optimization is the root of all evil." Understanding brute force deeply reveals exactly where the inefficiency lies—and guides us toward targeted improvements.

Observing Redundancy: The Path to Optimization

The key to optimizing the brute force approach is recognizing its redundant work. Where does the algorithm repeat computations that could be avoided?

Observation 1: Palindrome Structure is Hierarchical

If "abcba" is a palindrome, then its inner substring "bcb" must also be a palindrome. More generally:

A string S[i...j] is a palindrome if and only if:

S[i] = S[j], AND
S[i+1...j-1] is a palindrome (or j - i ≤ 1)

This recursive structure means checking "abcba" independently of "bcb" wastes the palindrome check we already did for "bcb".

Observation 2: Center Symmetry

Every palindrome has a center:

Odd-length palindromes have a single character center (e.g., 'c' in "abcba")
Even-length palindromes have a two-character center (e.g., "bb" in "abba")

Instead of checking every substring, we could check every possible center and expand outward. There are only 2n-1 centers (n single-character + n-1 between-character positions), potentially reducing the search space.

Observation 3: Wasted Comparisons

When we verify "bab" is a palindrome, we check:

s[0]='b' vs s[2]='b' ✓

Then when we verify "xbabx" (if it existed), we'd check:

s[0]='x' vs s[4]='x' ✓
s[1]='b' vs s[3]='b' ✓ (redundant—we already knew this)

The palindrome check doesn't leverage prior knowledge.

Preview of Optimizations

These observations lead directly to better algorithms:

• Expand Around Center (O(n²)): Exploits center symmetry—iterate over 2n-1 centers, expand outward until characters mismatch.

• Dynamic Programming (O(n²) time, O(n²) space): Exploits hierarchical structure—build a table where dp[i][j] indicates whether S[i...j] is a palindrome.

• Manacher's Algorithm (O(n)): Exploits all observations simultaneously—uses previously computed palindrome lengths to skip redundant checks.

Summary: Brute Force Approach

We've thoroughly explored the brute force approach to finding the longest palindromic substring. Let's consolidate the key takeaways:

Key Takeaways

•Problem Definition — The LPS problem asks for the longest contiguous palindromic substring of a given string. A palindrome reads the same forwards and backwards.
•Brute Force Strategy — Enumerate all O(n²) substrings, check each for the palindrome property in O(n) time, tracking the maximum length found.
•Time Complexity O(n³) — The triple nesting of operations makes this impractical for strings longer than ~1000 characters.
•Space Complexity O(1) — The algorithm uses only constant auxiliary space, a notable advantage over some optimized approaches.
•Educational Value — Brute force provides correctness guarantees, problem understanding, and a baseline for optimization discussions.
•Redundancy Identified — The hierarchical structure of palindromes and the center-based symmetry reveal opportunities for algorithmic improvement.

What's Next:

In the next page, we'll explore the Expand Around Center technique—a beautifully intuitive approach that reduces time complexity from O(n³) to O(n²) by leveraging the observation that every palindrome has a center. This technique is optimal for most practical scenarios and forms the foundation for understanding Manacher's linear-time algorithm.

Page Complete

You now understand the brute force approach to the longest palindromic substring problem. You can implement it correctly, analyze its O(n³) time complexity, and recognize the redundant work that optimization targets. Next, we'll transform these insights into the elegant expand-around-center technique.