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.

Practice

1. What is the main goal of the Longest Palindromic Substring problem?

easy

A. Count the total number of palindromic substrings

B. Reverse the string and compare with original

C. Check if the entire string is a palindrome

D. Find the longest substring that reads the same forwards and backwards

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the longest continuous part of the string that reads the same forwards and backwards.

2. Step 2: Differentiate from related problems

   Counting palindromic substrings or checking the whole string is different from finding the longest palindromic substring.

3. Final Answer:

   Find the longest substring that reads the same forwards and backwards -> Option D

4. Quick Check:

   Longest palindromic substring = Find longest palindrome [OK]

Hint: Longest palindrome means longest continuous mirrored substring [OK]

Common Mistakes:

• Confusing substring with subsequence
• Counting all palindromes instead of longest
• Checking whole string palindrome only

2. Which of the following Python code snippets correctly initializes variables to find the longest palindromic substring?

easy

A. start, max_len = 0, 1

B. start = max_len = None

C. start, max_len = 1, 0

D. start = max_len = 0

Solution

1. Step 1: Understand variable roles

   We need to track the start index and maximum length of the palindrome found. Starting with 0 and 1 is common because a single character is a palindrome.

2. Step 2: Check initialization correctness

   start, max_len = 0, 1 sets start=0 and max_len=1, which is correct. start, max_len = 1, 0 reverses values incorrectly. Options A, B, and C do not set max_len properly.

3. Final Answer:

   start, max_len = 0, 1 -> Option A

4. Quick Check:

   Initialize start=0 and max_len=1 for single char palindrome [OK]

Hint: Start at 0, max length at least 1 for single char palindrome [OK]

Common Mistakes:

• Setting max_len to 0 initially
• Using None instead of integers
• Swapping start and max_len values

3. What will be the output of the following code snippet?

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

s = "babad"
length = expand_around_center(s, 1, 1)
print(length)

medium

A. 1

B. 5

C. 3

D. 0

Solution

1. Step 1: Understand the function behavior

   The function expands around the center indices (left and right) while characters match, then returns the length of the palindrome found.

2. Step 2: Trace the expansion for s='babad' at center (1,1)

   Center at index 1 ('a'). Expand left=1, right=1: 'a'=='a' true, expand to left=0, right=2: 'b'=='b' true, expand to left=-1 (stop). Length = right - left - 1 = 3 - (-1) - 1 = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Expand around center returns palindrome length 3 [OK]

Hint: Expand while chars match, length = right - left - 1 [OK]

Common Mistakes:

• Not subtracting 1 in length calculation
• Confusing indices after expansion
• Assuming length equals right - left

4. Identify the error in the following code snippet for finding the longest palindromic substring:

def longest_palindrome(s):
    start, max_len = 0, 1
    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)
        len2 = expand_around_center(s, i, i+1)
        length = max(len1, len2)
        if length > max_len:
            start = i - length // 2
            max_len = length
    return s[start:start+max_len]

medium

A. The loop should run till len(s)-1 to avoid index error

B. The start index calculation is incorrect for even length palindromes

C. max_len should be initialized to 0 instead of 1

D. expand_around_center function is missing

Solution

1. Step 1: Analyze start index update logic

   For even length palindromes, start index calculation differs because center is between two characters. Using i - length // 2 works for odd length but not always for even length.

2. Step 2: Identify correct start calculation

   For even length, start should be i - (length // 2) + 1 to correctly locate the palindrome start.

3. Final Answer:

   The start index calculation is incorrect for even length palindromes -> Option B

4. Quick Check:

   Start index must adjust differently for even palindromes [OK]

Hint: Adjust start index differently for even-length palindromes [OK]

Common Mistakes:

• Using same start formula for odd and even palindromes
• Ignoring even length palindrome cases
• Not updating max_len properly

5. Given the string "forgeeksskeegfor", which substring is the longest palindromic substring?

hard

A. "geeksskeeg"

B. "forgeeksskeegfor"

C. "geeksskeegf"

D. "eksskeeg"

Solution

1. Step 1: Identify palindromic substrings in the string

   Check substrings that read the same forwards and backwards. "geeksskeeg" is a palindrome of length 10 inside the string.

2. Step 2: Compare lengths of candidate substrings

   "forgeeksskeegfor" is not a palindrome as a whole. "geeksskeegf" and "eksskeeg" are shorter palindromes.

3. Final Answer:

   "geeksskeeg" -> Option A

4. Quick Check:

   Longest palindrome in "forgeeksskeegfor" is "geeksskeeg" [OK]

Hint: Look for longest mirrored substring inside the string [OK]

Common Mistakes:

• Assuming whole string is palindrome
• Choosing substring with extra characters
• Ignoring palindrome length