Longest Palindromic Substring in DSA Python

Mental Model

Find the longest part of a string that reads the same forwards and backwards by checking around each character.

Analogy: Imagine looking for the biggest mirror in a hallway where the reflection looks exactly the same from both ends.

s = "b a b a d"
indexes: 0 1 2 3 4
Check centers ↑ at each letter and between letters for palindromes

Dry Run Walkthrough

Input: string: "babad"

Goal: Find the longest substring that reads the same forwards and backwards

Step 1: Check palindrome centered at index 0 ('b')

"b" -> palindrome length 1

Why: Every single letter is a palindrome of length 1

Step 2: Check palindrome centered between index 0 and 1 ('b' and 'a')

No palindrome longer than 1 found

Why: Characters differ, so no even length palindrome here

Step 3: Check palindrome centered at index 1 ('a')

"bab" -> palindrome length 3

Why: Expanding around 'a' finds 'bab' which reads same forwards and backwards

Step 4: Check palindrome centered between index 1 and 2 ('a' and 'b')

No palindrome longer than 1 found

Why: Characters differ, no even length palindrome here

Step 5: Check palindrome centered at index 2 ('b')

"aba" -> palindrome length 3

Why: Expanding around 'b' finds 'aba' which is palindrome

Step 6: Check palindrome centered between index 2 and 3 ('b' and 'a')

No palindrome longer than 1 found

Why: Characters differ, no even length palindrome here

Step 7: Check palindrome centered at index 3 ('a')

"a" -> palindrome length 1

Why: Single letter palindrome

Step 8: Check palindrome centered between index 3 and 4 ('a' and 'd')

No palindrome longer than 1 found

Why: Characters differ, no even length palindrome here

Step 9: Check palindrome centered at index 4 ('d')

"d" -> palindrome length 1

Why: Single letter palindrome

Result:

"bab" or "aba" are longest palindromic substrings

Annotated Code

DSA Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        start, end = 0, 0

        def expandAroundCenter(left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1

        for i in range(len(s)):
            len1 = expandAroundCenter(i, i)       # odd length palindrome
            len2 = expandAroundCenter(i, i + 1)   # even length palindrome
            max_len = max(len1, len2)
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2

        return s[start:end + 1]

# Driver code
sol = Solution()
input_str = "babad"
print(sol.longestPalindrome(input_str))

while left >= 0 and right < len(s) and s[left] == s[right]:

expand pointers outward while characters match to find palindrome length

len1 = expandAroundCenter(i, i)

check odd length palindrome centered at i

len2 = expandAroundCenter(i, i + 1)

check even length palindrome centered between i and i+1

if max_len > end - start:

update longest palindrome boundaries if found longer palindrome

start = i - (max_len - 1) // 2

calculate new start index of palindrome

end = i + max_len // 2

calculate new end index of palindrome

Output

bab

Complexity Analysis

Time: O(n^2) because for each character we expand around center which can take up to O(n) steps

Space: O(1) because we only use a few variables to track indices and lengths

vs Alternative: Compared to dynamic programming O(n^2) with O(n^2) space, this approach uses less space and is simpler

Edge Cases

empty string

returns empty string immediately

DSA Python

if not s:
    return ""

string with all identical characters, e.g. "aaaa"

returns the whole string as palindrome

DSA Python

while left >= 0 and right < len(s) and s[left] == s[right]:

string with no palindrome longer than 1, e.g. "abc"

returns any single character as palindrome

DSA Python

len1 = expandAroundCenter(i, i)

When to Use This Pattern

When asked to find the longest substring that reads the same forwards and backwards, use the expand around center pattern to check palindromes efficiently.

Common Mistakes

Mistake: Only checking odd length palindromes and missing even length ones
Fix: Check both odd (center at one character) and even (center between two characters) palindromes

Mistake: Not updating start and end indices correctly when a longer palindrome is found
Fix: Calculate start and end using the formula with max_len and current center index

Summary

Finds the longest substring that reads the same forwards and backwards in a given string.

Use when you need to identify the largest palindrome inside a string efficiently.

Check palindromes by expanding around each character and between characters to cover odd and even lengths.