Data Structures & AlgorithmsLongest Palindromic Substring

Longest Palindromic Substring

LevelIntermediate

Duration75 mins

TopicLongest Palindromic Substring

2 / 4

Expand Around Center Technique

The Elegant Middle-Out Approach

In the previous page, we explored the brute force approach to finding the longest palindromic substring—a correct but inefficient O(n³) algorithm. We observed that palindromes have a special structure: they're symmetric around their center. This observation leads to a beautifully intuitive optimization.

Instead of checking every possible substring from the outside in, what if we work from the inside out? For each possible center in the string, we can expand outward as long as the characters on both sides match. This simple shift in perspective transforms our O(n³) algorithm into an O(n²) solution.

The Expand Around Center technique is not just more efficient—it's also more elegant, easier to implement correctly, and forms the conceptual foundation for understanding Manacher's linear-time algorithm.

What You Will Learn

By the end of this page, you will master the expand-around-center technique. You'll understand why there are 2n-1 possible centers in a string of length n, how to expand from each center to find the longest palindrome, and why this approach achieves O(n²) time complexity with O(1) space.

The Center Insight

Every palindrome has a center—the point (or pair of points) around which the string is symmetric. This fundamental property enables a completely different algorithmic approach.

Odd-Length Palindromes

An odd-length palindrome has a single character at its center:

"aba" → center is 'b' at index 1
"racecar" → center is 'e' at index 3
"abcba" → center is 'c' at index 2

The center character matches itself, and matching characters extend symmetrically on both sides.

Even-Length Palindromes

An even-length palindrome has two characters at its center (or conceptually, the center lies between two characters):

"abba" → center is between indices 1 and 2 (between the two 'b's)
"noon" → center is between indices 1 and 2 (between the two 'o's)

The two center characters must match, and then matching continues symmetrically outward.

Palindrome Centers Analysis
Palindrome	Length	Type	Center Position	Center Character(s)
"a"	1	Odd	index 0	'a'
"aa"	2	Even	between 0,1	'a','a'
"aba"	3	Odd	index 1	'b'
"abba"	4	Even	between 1,2	'b','b'
"abcba"	5	Odd	index 2	'c'
"abccba"	6	Even	between 2,3	'c','c'
"racecar"	7	Odd	index 3	'e'

Counting Centers

For a string of length n, there are: • n character centers (for odd-length palindromes) • n-1 gap centers (for even-length palindromes) • Total: 2n-1 possible centers

This is the key insight! Instead of O(n²) substrings, we only have O(n) centers to consider.

The Expansion Process

The expand-around-center algorithm works by starting at a center and growing outward. Here's the process:

Step 1: Initialize at Center

For an odd-length palindrome centered at index c, start with left = c and right = c. For an even-length palindrome centered between indices c and c+1, start with left = c and right = c + 1.

Step 2: Expand While Matching

While left ≥ 0 and right < n and s[left] = s[right]:

Record the current palindrome length as right - left + 1
Decrement left (move left pointer leftward)
Increment right (move right pointer rightward)

Step 3: Stop When Mismatch or Boundary

The expansion stops when:

Characters don't match: s[left] ≠ s[right]
Left pointer goes below 0
Right pointer goes beyond n-1

The palindrome length is the last recorded length before stopping.

Visual Example: Expanding from Center

Consider s = "cbabad" and center at index 2 ('b'):

Initial:    c b a b a d
                ↑
            left=right=2 (center 'a')

Step 1:     c b a b a d
              ↑   ↑
            left=1, right=3
            s[1]='b' = s[3]='b' ✓
            Length = 3

Step 2:     c b a b a d
            ↑       ↑
            left=0, right=4
            s[0]='c' ≠ s[4]='a' ✗
            STOP

Result:     Longest palindrome centered at index 2 has length 3 ("bab")

Let's try center at index 3 ('b'):

Initial:    c b a b a d
                  ↑
            left=right=3 (center 'b')

Step 1:     c b a b a d
                ↑   ↑
            left=2, right=4
            s[2]='a' = s[4]='a' ✓
            Length = 3

Step 2:     c b a b a d
              ↑       ↑
            left=1, right=5
            s[1]='b' ≠ s[5]='d' ✗
            STOP

Result:     Longest palindrome centered at index 3 has length 3 ("aba")

The Expansion Helper Function

The core of the algorithm is a helper function that expands from a given center and returns the length of the longest palindrome found. This function handles both odd and even cases by accepting left and right starting positions.

expand_from_center.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
def expand_from_center(s: str, left: int, right: int) -> int:
    """
    Expand outward from the center defined by [left, right] and return
    the length of the longest palindrome found.
    
    For odd-length palindromes: left == right (single character center)
    For even-length palindromes: right == left + 1 (two character center)
    
    Args:
        s: The input string
        left: Left starting position
        right: Right starting position
    
    Returns:
        Length of the longest palindrome centered at this position
    
    Time Complexity: O(n) in the worst case (when entire string is palindrome)
    Space Complexity: O(1)
    """
    n = len(s)
    
    # Expand while within bounds and characters match
    while left >= 0 and right < n and s[left] == s[right]:
        left -= 1
        right += 1
    
    # When loop exits, [left+1, right-1] is the palindrome
    # Length = (right - 1) - (left + 1) + 1 = right - left - 1
    return right - left - 1
 
 
# Demonstrate the expansion process
text = "cbabad"
 
print("Odd-length expansions (single character centers):")
for i in range(len(text)):
    length = expand_from_center(text, i, i)
    start = i - length // 2
    end = start + length
    palindrome = text[start:end]
    print(f"  Center {i} ('{text[i]}'): length={length}, palindrome="{palindrome}"")
 
print("
Even-length expansions (between character centers):")
for i in range(len(text) - 1):
    length = expand_from_center(text, i, i + 1)
    if length > 0:
        start = i - (length - 2) // 2
        end = start + length
        palindrome = text[start:end]
        print(f"  Between {i},{i+1} ('{text[i]}','{text[i+1]}'): length={length}, palindrome="{palindrome}"")
    else:
        print(f"  Between {i},{i+1} ('{text[i]}','{text[i+1]}'): no palindrome")

Understanding the Length Calculation

When the while loop exits, left and right have moved one step beyond the palindrome boundaries. The actual palindrome spans from left+1 to right-1 (inclusive). The length formula right - left - 1 accounts for this: (right-1) - (left+1) + 1 = right - left - 1.

The Complete Expand Around Center Algorithm

Now let's combine the expansion helper with the main algorithm that iterates over all 2n-1 possible centers and tracks the longest palindrome found.

expand_around_center_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
79
80
81
82
83
84
85
86
def longest_palindrome_expand_center(s: str) -> str:
    """
    Find the longest palindromic substring using the expand-around-center technique.
    
    Algorithm:
    1. Consider each of the 2n-1 possible centers (n for odd, n-1 for even)
    2. Expand from each center to find the longest palindrome
    3. Track and return the overall longest palindrome
    
    Args:
        s: Input string
    
    Returns:
        The longest palindromic substring
    
    Time Complexity: O(n²)
        - O(n) centers to consider
        - O(n) expansion per center in worst case
        - Total: O(n × n) = O(n²)
    
    Space Complexity: O(1)
        - Only using a few variables for tracking
        - No auxiliary data structures
    """
    if not s:
        return ""
    
    n = len(s)
    
    # Track the start and end of the longest palindrome found
    start = 0
    max_length = 1
    
    def expand_from_center(left: int, right: int) -> int:
        """Expand from center and return palindrome length."""
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
    
    for i in range(n):
        # Odd-length palindrome centered at i
        len1 = expand_from_center(i, i)
        
        # Even-length palindrome centered between i and i+1
        len2 = expand_from_center(i, i + 1)
        
        # Take the longer of the two
        current_max = max(len1, len2)
        
        # Update if we found a longer palindrome
        if current_max > max_length:
            max_length = current_max
            # Calculate start position
            # For the palindrome of length max_length centered around i:
            # start = i - (max_length - 1) // 2
            start = i - (max_length - 1) // 2
    
    return s[start:start + max_length]
 
 
# Comprehensive test cases
test_cases = [
    ("babad", ["bab", "aba"]),
    ("cbbd", ["bb"]),
    ("a", ["a"]),
    ("ac", ["a", "c"]),
    ("racecar", ["racecar"]),
    ("", [""]),
    ("aaaa", ["aaaa"]),
    ("abcba", ["abcba"]),
    ("abaaba", ["abaaba"]),
    ("forgeeksskeegfor", ["geeksskeeg"]),
    ("abacdfgdcaba", ["aba"]),  # Multiple valid answers
    ("aaaabaaa", ["aaabaaa"]),
]
 
print("Expand Around Center LPS Testing")
print("=" * 60)
 
for s, expected in test_cases:
    result = longest_palindrome_expand_center(s)
    status = "✓" if result in expected else "✗"
    print(f"{status} Input: "{s}"")
    print(f"  Result: "{result}" (Length: {len(result)})")
    print()

Time Complexity Analysis

Let's rigorously analyze why the expand-around-center approach achieves O(n²) time complexity—a significant improvement over the O(n³) brute force.

Counting Operations

Outer Loop: We iterate through n positions (indices 0 to n-1), at each position considering both odd and even centers. This gives us 2n-1 centers total, which is O(n).

Expansion at Each Center: For each center, the expansion can visit at most O(n) characters in total (expanding to both boundaries). However, this is the worst case for any single center.

Key Insight: While any single expansion could take O(n), the total work across all expansions is bounded.

Detailed Analysis

Consider what happens when we expand from center i:

We might expand 0 steps (immediate mismatch)
We might expand k steps (matching k characters on each side)
Maximum expansion from center i is min(i, n-1-i) + 1 steps

The total number of character comparisons across all centers is at most:

$$\sum_{i=0}^{n-1} 2 \cdot \text{expansion}_i$$

In the worst case (string like "aaaa...a"), every expansion goes to the boundary:

Center 0: expands 0 steps (boundary)
Center 1: expands 1 step
Center n/2: expands n/2 steps (maximum)
...

The sum of expansions follows the pattern 0 + 1 + 2 + ... + n/2 + ... + 2 + 1 + 0, which sums to approximately n²/4.

Thus, total comparisons = O(n²).

Expand Around Center vs Brute Force Performance
String Length (n)	Brute Force O(n³)	Expand O(n²)	Speedup Factor
100	~170,000 ops	~10,000 ops	17×
1,000	~170,000,000 ops	~1,000,000 ops	170×
10,000	~170,000,000,000 ops	~100,000,000 ops	1,700×
100,000	~170 trillion ops	~10,000,000,000 ops	17,000×
1,000,000	~170 quadrillion ops	~1 trillion ops	170,000×

Practical Implications

For a string of length 10,000, brute force takes ~100 seconds while expand-around-center completes in ~0.1 seconds—a 1,000× speedup! The O(n²) complexity is practical for strings up to about 100,000 characters, handling the vast majority of real-world scenarios efficiently.

Space Complexity Analysis

The expand-around-center technique uses O(1) auxiliary space, making it optimal from a space perspective.

Variables Used:

start: Integer storing the starting index of the longest palindrome
max_length: Integer storing the length of the longest palindrome
left, right: Pointers for expansion
Loop variables (i)

All of these are single integers—constant space regardless of input size.

No Auxiliary Data Structures:

Unlike the dynamic programming approach (which we'll discuss later), expand-around-center doesn't need:

A 2D table of size n × n
Any precomputed arrays
Any hash maps or additional storage

The algorithm operates directly on the input string using only pointer manipulation.

Memory Efficiency Matters

For very long strings, memory usage can be a critical constraint. A DP approach requires O(n²) space—for a 100,000 character string, that's 10 billion boolean values (approximately 10GB of memory). The expand-around-center approach handles the same string with just a few bytes of auxiliary space.

Expand Around Center

•Time: O(n²)
•Space: O(1)
•Cache-friendly access pattern
•Simple implementation
•No preprocessing needed

Dynamic Programming

•Time: O(n²)
•Space: O(n²)
•Poor cache locality
•More complex indexing
•Requires table initialization

Edge Cases and Correctness

A robust implementation must handle all edge cases correctly. Let's examine the critical ones and verify our algorithm handles them properly.

Edge Case 1: Empty String

Input: "" Expected Output: ""

Our algorithm returns immediately for empty strings, which is correct.

Edge Case 2: Single Character

Input: "a" Expected Output: "a"

Expanding from center 0 gives length 1. The even-length expansion (between index 0 and 1) is not applicable since 1 ≥ n. Correct.

Edge Case 3: All Identical Characters

Input: "aaaa" Expected Output: "aaaa"

Expanding from any center will eventually hit the string boundaries, finding the full string as a palindrome. The center at index 1 or 2 will find the longest palindrome.

Edge Case Verification
Input	Edge Case Type	Expected	Handled By
""	Empty string	""	Early return check
"a"	Single character	"a"	Default max_length = 1
"ab"	No palindrome > 1	"a" or "b"	Each char is length-1 palindrome
"aa"	Even-length entire string	"aa"	Even expansion at center (0,1)
"aba"	Odd-length entire string	"aba"	Odd expansion at center 1
"aaaa"	All identical	"aaaa"	Maximum expansion from middle
"abcba"	Odd palindrome	"abcba"	Expansion from center
"abccba"	Even palindrome	"abccba"	Even expansion finds full

Common Implementation Bug

A frequent mistake is incorrectly calculating the start position from the maximum length and center. The formula start = i - (max_length - 1) // 2 works because: for a palindrome of length L centered at position i, it extends (L-1)/2 positions to the left. Always verify your start calculation with odd and even length examples.

Why This Works Better Than Brute Force

The expand-around-center approach achieves a fundamental reduction in work compared to brute force. Let's understand why.

Brute Force: Check All Substrings

The brute force approach treats all O(n²) substrings as independent entities:

Checking "abc" tells us nothing about "abcba"
Each substring is verified from scratch
No information is reused between checks

Expand Around Center: Grow From Centers

The expand approach exploits palindrome structure:

A palindrome grows from its center
If "bcb" is a palindrome, checking "abcba" only requires verifying the new outer characters
Expansions naturally share the inner palindrome verification

The Key Insight

Brute force asks: "Is this substring a palindrome?" independently for each substring.

Expand-around-center asks: "How far can this palindrome extend?" from each center.

The second question inherently builds on previous work within each expansion.

Why Expansion Is More Efficient

•Eliminates Redundant Verification: When expanding from center, each character comparison contributes to the final answer. No wasted work on non-extendable palindromes.
•Natural Early Termination: Expansion stops as soon as characters mismatch. Brute force must verify entire substrings even if mismatch is at the start.
•Exploits Locality: Expanding from a center keeps memory access patterns local, improving cache performance on modern processors.
•Simpler Control Flow: Two nested loops with clear termination conditions, versus three levels of iteration in brute force.

Summary: Expand Around Center Technique

We've thoroughly explored the expand-around-center technique—a significant improvement over brute force for finding the longest palindromic substring.

Key Takeaways

•Center-Based Insight — Every palindrome has a center (single character for odd length, pair for even). A string of length n has 2n-1 possible centers.
•Expansion Process — From each center, expand outward while characters match. The algorithm naturally finds the longest palindrome for each center.
•Time Complexity O(n²) — O(n) centers × O(n) expansion per center. Significantly faster than O(n³) brute force.
•Space Complexity O(1) — Uses only a constant number of variables. No auxiliary data structures required.
•Practical Efficiency — Handles strings up to ~100,000 characters efficiently. Preferred solution for most real-world scenarios.
•Clean Implementation — Simple, readable code with clear logic. Fewer opportunities for bugs than more complex approaches.

What's Next:

In the next page, we'll explore Manacher's Algorithm—a brilliant technique that achieves O(n) time complexity by reusing information from previously computed palindrome lengths. Manacher's algorithm transforms the string to handle odd/even cases uniformly and uses clever observations about palindrome symmetry to avoid redundant work.

Page Complete

You now understand the expand-around-center technique. You can implement it correctly, analyze its O(n²) time and O(1) space complexity, and explain why it's superior to brute force. This technique is the recommended solution for most interview and practical scenarios. Next, we'll explore how Manacher's algorithm achieves linear time.

2 / 4

Loading learning content...

Data Structures & AlgorithmsLongest Palindromic Substring

Longest Palindromic Substring

LevelIntermediate

Duration75 mins

TopicLongest Palindromic Substring

2 / 4

Expand Around Center Technique

The Elegant Middle-Out Approach

What You Will Learn

The Center Insight

Every palindrome has a center—the point (or pair of points) around which the string is symmetric. This fundamental property enables a completely different algorithmic approach.

Odd-Length Palindromes

An odd-length palindrome has a single character at its center:

"aba" → center is 'b' at index 1
"racecar" → center is 'e' at index 3
"abcba" → center is 'c' at index 2

The center character matches itself, and matching characters extend symmetrically on both sides.

Even-Length Palindromes

An even-length palindrome has two characters at its center (or conceptually, the center lies between two characters):

"abba" → center is between indices 1 and 2 (between the two 'b's)
"noon" → center is between indices 1 and 2 (between the two 'o's)

The two center characters must match, and then matching continues symmetrically outward.

Palindrome Centers Analysis
Palindrome	Length	Type	Center Position	Center Character(s)
"a"	1	Odd	index 0	'a'
"aa"	2	Even	between 0,1	'a','a'
"aba"	3	Odd	index 1	'b'
"abba"	4	Even	between 1,2	'b','b'
"abcba"	5	Odd	index 2	'c'
"abccba"	6	Even	between 2,3	'c','c'
"racecar"	7	Odd	index 3	'e'

Counting Centers

For a string of length n, there are: • n character centers (for odd-length palindromes) • n-1 gap centers (for even-length palindromes) • Total: 2n-1 possible centers

This is the key insight! Instead of O(n²) substrings, we only have O(n) centers to consider.

The Expansion Process

The expand-around-center algorithm works by starting at a center and growing outward. Here's the process:

Step 1: Initialize at Center

Step 2: Expand While Matching

While left ≥ 0 and right < n and s[left] = s[right]:

Record the current palindrome length as right - left + 1
Decrement left (move left pointer leftward)
Increment right (move right pointer rightward)

Step 3: Stop When Mismatch or Boundary

The expansion stops when:

Characters don't match: s[left] ≠ s[right]
Left pointer goes below 0
Right pointer goes beyond n-1

The palindrome length is the last recorded length before stopping.

Visual Example: Expanding from Center

Consider s = "cbabad" and center at index 2 ('b'):

Initial:    c b a b a d
                ↑
            left=right=2 (center 'a')

Step 1:     c b a b a d
              ↑   ↑
            left=1, right=3
            s[1]='b' = s[3]='b' ✓
            Length = 3

Step 2:     c b a b a d
            ↑       ↑
            left=0, right=4
            s[0]='c' ≠ s[4]='a' ✗
            STOP

Result:     Longest palindrome centered at index 2 has length 3 ("bab")

Let's try center at index 3 ('b'):

Initial:    c b a b a d
                  ↑
            left=right=3 (center 'b')

Step 1:     c b a b a d
                ↑   ↑
            left=2, right=4
            s[2]='a' = s[4]='a' ✓
            Length = 3

Step 2:     c b a b a d
              ↑       ↑
            left=1, right=5
            s[1]='b' ≠ s[5]='d' ✗
            STOP

Result:     Longest palindrome centered at index 3 has length 3 ("aba")

The Expansion Helper Function

expand_from_center.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
def expand_from_center(s: str, left: int, right: int) -> int:
    """
    Expand outward from the center defined by [left, right] and return
    the length of the longest palindrome found.
    
    For odd-length palindromes: left == right (single character center)
    For even-length palindromes: right == left + 1 (two character center)
    
    Args:
        s: The input string
        left: Left starting position
        right: Right starting position
    
    Returns:
        Length of the longest palindrome centered at this position
    
    Time Complexity: O(n) in the worst case (when entire string is palindrome)
    Space Complexity: O(1)
    """
    n = len(s)
    
    # Expand while within bounds and characters match
    while left >= 0 and right < n and s[left] == s[right]:
        left -= 1
        right += 1
    
    # When loop exits, [left+1, right-1] is the palindrome
    # Length = (right - 1) - (left + 1) + 1 = right - left - 1
    return right - left - 1
 
 
# Demonstrate the expansion process
text = "cbabad"
 
print("Odd-length expansions (single character centers):")
for i in range(len(text)):
    length = expand_from_center(text, i, i)
    start = i - length // 2
    end = start + length
    palindrome = text[start:end]
    print(f"  Center {i} ('{text[i]}'): length={length}, palindrome="{palindrome}"")
 
print("
Even-length expansions (between character centers):")
for i in range(len(text) - 1):
    length = expand_from_center(text, i, i + 1)
    if length > 0:
        start = i - (length - 2) // 2
        end = start + length
        palindrome = text[start:end]
        print(f"  Between {i},{i+1} ('{text[i]}','{text[i+1]}'): length={length}, palindrome="{palindrome}"")
    else:
        print(f"  Between {i},{i+1} ('{text[i]}','{text[i+1]}'): no palindrome")

Understanding the Length Calculation

The Complete Expand Around Center Algorithm

Now let's combine the expansion helper with the main algorithm that iterates over all 2n-1 possible centers and tracks the longest palindrome found.

expand_around_center_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
79
80
81
82
83
84
85
86
def longest_palindrome_expand_center(s: str) -> str:
    """
    Find the longest palindromic substring using the expand-around-center technique.
    
    Algorithm:
    1. Consider each of the 2n-1 possible centers (n for odd, n-1 for even)
    2. Expand from each center to find the longest palindrome
    3. Track and return the overall longest palindrome
    
    Args:
        s: Input string
    
    Returns:
        The longest palindromic substring
    
    Time Complexity: O(n²)
        - O(n) centers to consider
        - O(n) expansion per center in worst case
        - Total: O(n × n) = O(n²)
    
    Space Complexity: O(1)
        - Only using a few variables for tracking
        - No auxiliary data structures
    """
    if not s:
        return ""
    
    n = len(s)
    
    # Track the start and end of the longest palindrome found
    start = 0
    max_length = 1
    
    def expand_from_center(left: int, right: int) -> int:
        """Expand from center and return palindrome length."""
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1
    
    for i in range(n):
        # Odd-length palindrome centered at i
        len1 = expand_from_center(i, i)
        
        # Even-length palindrome centered between i and i+1
        len2 = expand_from_center(i, i + 1)
        
        # Take the longer of the two
        current_max = max(len1, len2)
        
        # Update if we found a longer palindrome
        if current_max > max_length:
            max_length = current_max
            # Calculate start position
            # For the palindrome of length max_length centered around i:
            # start = i - (max_length - 1) // 2
            start = i - (max_length - 1) // 2
    
    return s[start:start + max_length]
 
 
# Comprehensive test cases
test_cases = [
    ("babad", ["bab", "aba"]),
    ("cbbd", ["bb"]),
    ("a", ["a"]),
    ("ac", ["a", "c"]),
    ("racecar", ["racecar"]),
    ("", [""]),
    ("aaaa", ["aaaa"]),
    ("abcba", ["abcba"]),
    ("abaaba", ["abaaba"]),
    ("forgeeksskeegfor", ["geeksskeeg"]),
    ("abacdfgdcaba", ["aba"]),  # Multiple valid answers
    ("aaaabaaa", ["aaabaaa"]),
]
 
print("Expand Around Center LPS Testing")
print("=" * 60)
 
for s, expected in test_cases:
    result = longest_palindrome_expand_center(s)
    status = "✓" if result in expected else "✗"
    print(f"{status} Input: "{s}"")
    print(f"  Result: "{result}" (Length: {len(result)})")
    print()

Time Complexity Analysis

Let's rigorously analyze why the expand-around-center approach achieves O(n²) time complexity—a significant improvement over the O(n³) brute force.

Counting Operations

Outer Loop: We iterate through n positions (indices 0 to n-1), at each position considering both odd and even centers. This gives us 2n-1 centers total, which is O(n).

Expansion at Each Center: For each center, the expansion can visit at most O(n) characters in total (expanding to both boundaries). However, this is the worst case for any single center.

Key Insight: While any single expansion could take O(n), the total work across all expansions is bounded.

Detailed Analysis

Consider what happens when we expand from center i:

We might expand 0 steps (immediate mismatch)
We might expand k steps (matching k characters on each side)
Maximum expansion from center i is min(i, n-1-i) + 1 steps

The total number of character comparisons across all centers is at most:

$$\sum_{i=0}^{n-1} 2 \cdot \text{expansion}_i$$

In the worst case (string like "aaaa...a"), every expansion goes to the boundary:

Center 0: expands 0 steps (boundary)
Center 1: expands 1 step
Center n/2: expands n/2 steps (maximum)
...

The sum of expansions follows the pattern 0 + 1 + 2 + ... + n/2 + ... + 2 + 1 + 0, which sums to approximately n²/4.

Thus, total comparisons = O(n²).

Expand Around Center vs Brute Force Performance
String Length (n)	Brute Force O(n³)	Expand O(n²)	Speedup Factor
100	~170,000 ops	~10,000 ops	17×
1,000	~170,000,000 ops	~1,000,000 ops	170×
10,000	~170,000,000,000 ops	~100,000,000 ops	1,700×
100,000	~170 trillion ops	~10,000,000,000 ops	17,000×
1,000,000	~170 quadrillion ops	~1 trillion ops	170,000×

Practical Implications

Space Complexity Analysis

The expand-around-center technique uses O(1) auxiliary space, making it optimal from a space perspective.

Variables Used:

start: Integer storing the starting index of the longest palindrome
max_length: Integer storing the length of the longest palindrome
left, right: Pointers for expansion
Loop variables (i)

All of these are single integers—constant space regardless of input size.

No Auxiliary Data Structures:

Unlike the dynamic programming approach (which we'll discuss later), expand-around-center doesn't need:

A 2D table of size n × n
Any precomputed arrays
Any hash maps or additional storage

The algorithm operates directly on the input string using only pointer manipulation.

Memory Efficiency Matters

Expand Around Center

•Time: O(n²)
•Space: O(1)
•Cache-friendly access pattern
•Simple implementation
•No preprocessing needed

Dynamic Programming

•Time: O(n²)
•Space: O(n²)
•Poor cache locality
•More complex indexing
•Requires table initialization

Edge Cases and Correctness

A robust implementation must handle all edge cases correctly. Let's examine the critical ones and verify our algorithm handles them properly.

Edge Case 1: Empty String

Input: "" Expected Output: ""

Our algorithm returns immediately for empty strings, which is correct.

Edge Case 2: Single Character

Input: "a" Expected Output: "a"

Expanding from center 0 gives length 1. The even-length expansion (between index 0 and 1) is not applicable since 1 ≥ n. Correct.

Edge Case 3: All Identical Characters

Input: "aaaa" Expected Output: "aaaa"

Expanding from any center will eventually hit the string boundaries, finding the full string as a palindrome. The center at index 1 or 2 will find the longest palindrome.

Edge Case Verification
Input	Edge Case Type	Expected	Handled By
""	Empty string	""	Early return check
"a"	Single character	"a"	Default max_length = 1
"ab"	No palindrome > 1	"a" or "b"	Each char is length-1 palindrome
"aa"	Even-length entire string	"aa"	Even expansion at center (0,1)
"aba"	Odd-length entire string	"aba"	Odd expansion at center 1
"aaaa"	All identical	"aaaa"	Maximum expansion from middle
"abcba"	Odd palindrome	"abcba"	Expansion from center
"abccba"	Even palindrome	"abccba"	Even expansion finds full

Common Implementation Bug

Why This Works Better Than Brute Force

The expand-around-center approach achieves a fundamental reduction in work compared to brute force. Let's understand why.

Brute Force: Check All Substrings

The brute force approach treats all O(n²) substrings as independent entities:

Checking "abc" tells us nothing about "abcba"
Each substring is verified from scratch
No information is reused between checks

Expand Around Center: Grow From Centers

The expand approach exploits palindrome structure:

A palindrome grows from its center
If "bcb" is a palindrome, checking "abcba" only requires verifying the new outer characters
Expansions naturally share the inner palindrome verification

The Key Insight

Brute force asks: "Is this substring a palindrome?" independently for each substring.

Expand-around-center asks: "How far can this palindrome extend?" from each center.

The second question inherently builds on previous work within each expansion.

Why Expansion Is More Efficient

•Eliminates Redundant Verification: When expanding from center, each character comparison contributes to the final answer. No wasted work on non-extendable palindromes.
•Natural Early Termination: Expansion stops as soon as characters mismatch. Brute force must verify entire substrings even if mismatch is at the start.
•Exploits Locality: Expanding from a center keeps memory access patterns local, improving cache performance on modern processors.
•Simpler Control Flow: Two nested loops with clear termination conditions, versus three levels of iteration in brute force.

Summary: Expand Around Center Technique

We've thoroughly explored the expand-around-center technique—a significant improvement over brute force for finding the longest palindromic substring.

Key Takeaways

•Center-Based Insight — Every palindrome has a center (single character for odd length, pair for even). A string of length n has 2n-1 possible centers.
•Expansion Process — From each center, expand outward while characters match. The algorithm naturally finds the longest palindrome for each center.
•Time Complexity O(n²) — O(n) centers × O(n) expansion per center. Significantly faster than O(n³) brute force.
•Space Complexity O(1) — Uses only a constant number of variables. No auxiliary data structures required.
•Practical Efficiency — Handles strings up to ~100,000 characters efficiently. Preferred solution for most real-world scenarios.
•Clean Implementation — Simple, readable code with clear logic. Fewer opportunities for bugs than more complex approaches.

What's Next:

Page Complete

2 / 4