Longest Palindromic Substring in DSA Rust - Execution Trace

Concept Flow - Longest Palindromic Substring

Start

↓

Pick center index i

↓

Expand around i (odd length)

↓

Expand around i and i+1 (even length)

↓

Update longest palindrome if found

↓

Move to next center i+1

↓

Repeat until all centers checked

↓

Return longest palindrome substring

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

Execution Sample

DSA Rust

fn longest_palindrome(s: &str) -> String {
    let chars: Vec<char> = s.chars().collect();
    let mut start = 0;
    let mut max_len = 1;
    for i in 0..chars.len() {
        // expand around center
    }
    s[start..start+max_len].to_string()
}

This code finds the longest palindromic substring by expanding around each center index.

Execution Table

Step	Operation	Center Index(es)	Palindrome Found	Longest Palindrome Start	Longest Palindrome Length	Visual State
1	Pick center i=0 (odd)	0	"a"	0	1	"a"
2	Expand around i=0 (even)	0,1	"a"	0	1	"a"
3	Pick center i=1 (odd)	1	"b"	0	1	"a"
4	Expand around i=1,2 (even)	1,2	"bb"	1	2	"abb" (longest "bb")
5	Pick center i=2 (odd)	2	"b"	1	2	"abb"
6	Expand around i=2,3 (even)	2,3	"b"	1	2	"abb"
7	Pick center i=3 (odd)	3	"a"	1	2	"abb"
8	Expand around i=3,4 (even)	3,4	"a"	1	2	"abb"
9	Pick center i=4 (odd)	4	"c"	1	2	"abb"
10	Expand around i=4,5 (even)	4,5	"c"	1	2	"abb"
11	Pick center i=5 (odd)	5	"a"	1	2	"abb"
12	Expand around i=5,6 (even)	5,6	"a"	1	2	"abb"
13	Pick center i=6 (odd)	6	"d"	1	2	"abb"
14	Expand around i=6,7 (even)	6,7	"d"	1	2	"abb"
15	Pick center i=7 (odd)	7	"a"	1	2	"abb"
16	Expand around i=7,8 (even)	7,8	"a"	1	2	"abb"
17	Pick center i=8 (odd)	8	"a"	1	2	"abb"
18	Expand around i=8,9 (even)	8,9	"a"	1	2	"abb"
19	End of centers	-	-	1	2	"bb" is longest palindrome
20	Return substring	-	-	1	2	"bb"

💡 All center indices checked, longest palindrome found is "bb" starting at index 1 with length 2.

Variable Tracker

Variable	Start	After Step 4	After Step 19	Final
start	0	1	1	1
max_len	1	2	2	2
current palindrome	"a"	"bb"	"bb"	"bb"

Key Moments - 3 Insights

Why do we check both odd and even length centers?

Because palindromes can be odd length (single center) or even length (center between two chars). See steps 1 and 2 in execution_table.

Why does the longest palindrome start update only sometimes?

It updates only when a longer palindrome is found during expansion, as shown at step 4 where "bb" updates start to 1 and max_len to 2.

What happens when expansion cannot continue?

Expansion stops when characters at left and right pointers differ or go out of bounds, ending that center's check, as implied in all expansion steps.

Visual Quiz - 3 Questions

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

A "bb"

B "a"

C "b"

D "abb"

💡 Hint

Check the 'Longest Palindrome Length' and 'Visual State' columns at step 4.

At which step does the algorithm finish checking all centers?

A Step 16

B Step 20

C Step 19

D Step 10

💡 Hint

Look for the row with 'End of centers' in the 'Operation' column.

If the input string was "aaa", what would the max_len be after checking center i=1 (odd)?

A 2

B 3

C 1

D 0

💡 Hint

Consider expansion around center i=1 for odd length palindrome in a string of repeated characters.

Concept Snapshot

Longest Palindromic Substring:
- Check each index as center
- Expand left and right while chars match
- Check odd (single center) and even (two centers)
- Track start and max length
- Return substring from start with max length

Full Transcript

The Longest Palindromic Substring algorithm works by checking each character index as a center and expanding outwards to find palindromes. It considers both odd length palindromes (single center) and even length palindromes (center between two characters). For each center, it expands left and right as long as characters match. When a longer palindrome is found, it updates the start index and maximum length. After checking all centers, it returns the longest palindrome substring found. The execution table shows step-by-step how the center indices are chosen, expansions performed, and the longest palindrome updated. Key moments clarify why both odd and even centers are needed and when updates happen. The visual quiz tests understanding of the longest palindrome state at various steps.

Practice

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

easy

A. Find the longest substring that contains only vowels

B. Find the longest substring with all unique characters

C. Find the longest substring with increasing characters

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

Solution

1. Step 1: Understand palindrome definition

   A palindrome reads the same forwards and backwards, like 'madam' or 'racecar'.

2. Step 2: Identify problem goal

   The problem asks to find the longest continuous part of a string that is a palindrome.

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: Look for substring that mirrors itself [OK]

Common Mistakes:

• Confusing substring with subsequence
• Looking for unique characters instead of palindrome
• Ignoring continuous substring requirement

2. Which Rust code snippet correctly declares a function header for finding the longest palindromic substring in a string slice s?

easy

A. fn longest_palindrome(s: &str) -> &str { }

B. fn longest_palindrome(s: String) -> String { }

C. fn longest_palindrome(s: &String) -> &String { }

D. fn longest_palindrome(s: str) -> str { }

Solution

1. Step 1: Understand Rust string types

   Rust uses &str for string slices and String for owned strings.

2. Step 2: Choose correct function signature

   Function should take a string slice &str and return a string slice &str for substring references.

3. Final Answer:

   fn longest_palindrome(s: &str) -> &str { } -> Option A

4. Quick Check:

   Use &str for slices in function signature [OK]

Hint: Use &str for input and output substrings [OK]

Common Mistakes:

• Using owned String when slice is better
• Returning owned String unnecessarily
• Incorrect parameter types like str without &

3. What will be the output of the following Rust code snippet that finds the longest palindromic substring?

fn main() {
    let s = "babad";
    let result = longest_palindrome(s);
    println!("{}", result);
}

fn longest_palindrome(s: &str) -> &str {
    let chars: Vec<char> = s.chars().collect();
    let mut start = 0;
    let mut max_len = 1;

    for i in 0..chars.len() {
        let mut left = i as i32;
        let mut right = i as i32;

        while left >= 0 && right < chars.len() as i32 && chars[left as usize] == chars[right as usize] {
            if (right - left + 1) > max_len {
                start = left as usize;
                max_len = (right - left + 1) as usize;
            }
            left -= 1;
            right += 1;
        }
    }

    &s[start..start + max_len]
}

medium

A. aba

B. bad

C. bab

D. babad

Solution

1. Step 1: Understand the code logic

   The code expands around each character to find odd-length palindromes and tracks the longest.

2. Step 2: Trace the input "babad"

   At index 0: palindrome "b" (length 1), index 1: "bab" (length 3), index 2: "aba" (length 3). The first longest palindrome found is "bab".

3. Final Answer:

   bab -> Option C

4. Quick Check:

   Longest palindrome substring = bab [OK]

Hint: Expand around center, pick first longest palindrome [OK]

Common Mistakes:

• Assuming palindrome must be unique
• Returning entire string instead of substring
• Confusing substring indices

4. Identify the bug in this Rust function that tries to find the longest palindromic substring:

fn longest_palindrome(s: &str) -> &str {
    let chars: Vec<char> = s.chars().collect();
    let mut start = 0;
    let mut max_len = 1;

    for i in 0..chars.len() {
        let mut left = i as i32;
        let mut right = i as i32 + 1;

        while left >= 0 && right < chars.len() as i32 && chars[left as usize] == chars[right as usize] {
            if (right - left + 1) > max_len {
                start = left as usize;
                max_len = (right - left + 1) as usize;
            }
            left -= 1;
            right += 1;
        }
    }

    &s[start..start + max_len]
}

medium

A. The max_len should start at 0, not 1

B. The initial right pointer should be equal to i, not i + 1

C. The loop should iterate from 1 to length, not 0 to length

D. The function should return a String, not &str

Solution

1. Step 1: Analyze pointer initialization

   Right pointer starts at i + 1, which only checks even-length palindromes, missing odd-length ones.

2. Step 2: Correct pointer for odd-length palindromes

   To check odd-length palindromes, right pointer should start at i, same as left pointer.

3. Final Answer:

   The initial right pointer should be equal to i, not i + 1 -> Option B

4. Quick Check:

   Right pointer = i for odd-length palindrome check [OK]

Hint: Start right pointer same as left for odd palindromes [OK]

Common Mistakes:

• Only checking even-length palindromes
• Wrong loop range causing index errors
• Returning wrong type causing borrow issues

5. Given the string "forgeeksskeegfor", which approach correctly finds the longest palindromic substring and what is that substring?

hard

A. Expand around center method; longest palindrome is "geeksskeeg"

B. Dynamic programming with substring table; longest palindrome is "forgeeksskeegfor"

C. Brute force checking all substrings; longest palindrome is "ss"

D. Using hash map for character counts; longest palindrome is "ks"

Solution

1. Step 1: Understand approaches to find longest palindrome

   Expand around center and dynamic programming are common methods; brute force is slow but correct.

2. Step 2: Identify longest palindrome in given string

   "forgeeksskeegfor" contains "geeksskeeg" as the longest palindrome substring, not the entire string.

3. Step 3: Match approach and answer

   Expand around center method efficiently finds "geeksskeeg"; dynamic programming would too but not the full string.

4. Final Answer:

   Expand around center method; longest palindrome is "geeksskeeg" -> Option A

5. Quick Check:

   Longest palindrome = geeksskeeg by center expansion [OK]

Hint: Expand around centers to find longest palindrome fast [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Using character counts instead of substring checks
• Confusing brute force with efficient methods