Longest Palindromic Substring in DSA Python - Execution Trace

Concept Flow - Longest Palindromic Substring

Start at each index i in string

↓

Expand around center i (odd length)

↓

Expand around center i and i+1 (even length)

↓

Check palindrome length

↓

Update longest palindrome if longer

↓

Move to next index i+1

↓

End

We check each position as a center and expand outwards to find palindromes, updating the longest found.

Execution Sample

DSA Python

def longest_palindrome(s):
    start = 0
    max_len = 1
    for i in range(len(s)):
        # Odd length palindrome
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
        # Even length palindrome
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > max_len:
                start = l
                max_len = r - l + 1
            l -= 1
            r += 1
    return s[start:start+max_len]

This code finds the longest palindrome by expanding around each character for odd length and around each pair for even length palindromes.

Execution Table

Step	Operation	Center Indices (l,r)	Palindrome Checked	Longest Palindrome	Visual State
1	Start at index 0	l=0, r=0	"a"	"a"	"a"
2	Expand around center 0	l=-1, r=1	Stop (l<0)	"a"	"a"
3	Start at index 1	l=1, r=1	"b"	"a"	"a"
4	Expand around center 1	l=0, r=2	"aba"	"aba"	"aba"
5	Expand around center 1	l=-1, r=3	Stop (l<0)	"aba"	"aba"
6	Start at index 2	l=2, r=2	"a"	"aba"	"aba"
7	Expand around center 2	l=1, r=3	"bab"	"aba"	"aba"
8	Expand around center 2	l=0, r=4	"ababa"	"ababa"	"ababa"
9	Expand around center 2	l=-1, r=5	Stop (l<0)	"ababa"	"ababa"
10	Start at index 3	l=3, r=3	"b"	"ababa"	"ababa"
11	Expand around center 3	l=2, r=4	"aba"	"ababa"	"ababa"
12	Expand around center 3	l=1, r=5	Stop (r>=len)	"ababa"	"ababa"
13	Start at index 4	l=4, r=4	"a"	"ababa"	"ababa"
14	Expand around center 4	l=3, r=5	Stop (r>=len)	"ababa"	"ababa"
15	End of string reached	-	-	"ababa"	"ababa"

💡 All centers checked, longest palindrome found is "ababa"

Variable Tracker

Variable	Start	After Step 4	After Step 8	After Step 15
start	0	0	0	0
max_len	1	3	5	5
l	-	0	0	-
r	-	2	4	-

Key Moments - 3 Insights

Why do we expand around two centers (i and i+1) for even length palindromes?

For even length palindromes, we expand around i and i+1 to catch palindromes like "abba". The original code only expands around one center, so even length palindromes are missed. The updated code includes expansion around both centers.

Why does the expansion stop when l < 0 or r >= len(s)?

Because l and r represent indices expanding outwards. If l < 0 or r >= len(s), we are outside the string bounds, so we cannot check further. This is shown in steps 2, 5, 9, 12, and 14 where expansion stops.

How is the longest palindrome updated during expansion?

At each expansion, if the current palindrome length (r - l + 1) is greater than max_len, we update start and max_len. For example, at step 4, max_len changes from 1 to 3 and start to 0, and at step 8, max_len updates to 5 and start to 0.

Visual Quiz - 3 Questions

Look at the execution table, what is the longest palindrome after step 4?

A "aba"

B "b"

C "a"

D "ababa"

💡 Hint

Check the 'Longest Palindrome' column at step 4 in the execution_table.

At which step does the palindrome length first update to 5?

A Step 12

B Step 5

C Step 8

D Step 15

💡 Hint

Look at the 'Longest Palindrome' column and find when it changes to "ababa".

If we added even length palindrome checks, which step would change?

A Step 1

B Step 6

C Step 3

D Step 14

💡 Hint

Even length checks happen around centers i and i+1, which is done at each index like step 6.

Concept Snapshot

Longest Palindromic Substring:
- Check each index as palindrome center
- Expand left and right while chars match
- Update longest substring if longer found
- Repeat for all indices
- Return substring from start with max length

Full Transcript

The longest palindromic substring is found by checking each character as a center and expanding outwards to see if the characters on both sides match. We keep track of the longest palindrome found so far by updating the start index and maximum length. Expansion stops when indices go out of string bounds or characters don't match. This example checks both odd length palindromes by expanding around one center and even length palindromes by expanding around two centers. The final longest palindrome substring is returned after checking all centers.