Longest Palindromic Substring in DSA Rust

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 matches perfectly on both sides of a point.

s = "b a b a d"
indexes: 0 1 2 3 4
Check centers ↑ at each index and expand outwards to find 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 (odd length): 'b'

"b" -> palindrome length 1

Why: Start by checking smallest palindrome at first character.

Step 2: Check palindrome centered between index 0 and 1 (even length): no palindrome longer than 0

No even length palindrome found here

Why: Check even length palindromes between characters.

Step 3: Check palindrome centered at index 1 (odd length): expand 'a' -> 'bab'

"bab" -> palindrome length 3

Why: Expand around center to find longer palindrome.

Step 4: Check palindrome centered between index 1 and 2 (even length): no palindrome longer than 0

No even length palindrome found here

Why: Check even length palindromes between characters.

Step 5: Check palindrome centered at index 2 (odd length): expand 'b' -> 'aba'

"aba" -> palindrome length 3

Why: Another palindrome of length 3 found.

Step 6: Check palindrome centered between index 2 and 3 (even length): no palindrome longer than 0

No even length palindrome found here

Why: Check even length palindromes between characters.

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

"a" -> palindrome length 1

Why: Single character palindrome.

Step 8: Check palindrome centered between index 3 and 4 (even length): no palindrome longer than 0

No even length palindrome found here

Why: Check even length palindromes between characters.

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

"d" -> palindrome length 1

Why: Single character palindrome.

Result:

"bab" or "aba" are the longest palindromic substrings

Annotated Code

DSA Rust

fn longest_palindrome(s: &str) -> String {
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();
    if n == 0 {
        return String::new();
    }

    let mut start = 0;
    let mut max_len = 1;

    // Helper function to expand around center
    fn expand_around_center(chars: &Vec<char>, left: usize, right: usize) -> (usize, usize) {
        let mut l = left as isize;
        let mut r = right as isize;
        let n = chars.len() as isize;
        while l >= 0 && r < n && chars[l as usize] == chars[r as usize] {
            l -= 1;
            r += 1;
        }
        // Return start and length of palindrome
        ((l + 1) as usize, (r - l - 1) as usize)
    }

    for i in 0..n {
        // Odd length palindrome
        let (l1, len1) = expand_around_center(&chars, i, i);
        if len1 > max_len {
            start = l1;
            max_len = len1;
        }
        // Even length palindrome
        if i + 1 < n {
            let (l2, len2) = expand_around_center(&chars, i, i + 1);
            if len2 > max_len {
                start = l2;
                max_len = len2;
            }
        }
    }

    chars[start..start + max_len].iter().collect()
}

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

while l >= 0 && r < n && chars[l as usize] == chars[r as usize] {

expand pointers outward while characters match to find palindrome bounds

for i in 0..n {

iterate over each character as potential palindrome center

let (l1, len1) = expand_around_center(&chars, i, i);

check odd length palindrome centered at i

if len1 > max_len { start = l1; max_len = len1; }

update longest palindrome if found longer odd length

if i + 1 < n { let (l2, len2) = expand_around_center(&chars, i, i + 1);

check even length palindrome centered between i and i+1

if len2 > max_len { start = l2; max_len = len2; }

update longest palindrome if found longer even length

Output

bab

Complexity Analysis

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

Space: O(n) for storing characters of the string

vs Alternative: This is faster and simpler than checking all substrings (O(n^3)) but slower than Manacher's algorithm (O(n)) which is more complex

Edge Cases

empty string

returns empty string immediately

DSA Rust

if n == 0 { return String::new(); }

string with all identical characters

returns the entire string as palindrome

DSA Rust

while l >= 0 && r < n && chars[l as usize] == chars[r as usize]

string with no palindrome longer than 1

returns any single character substring

DSA Rust

max_len initialized to 1 and updated only if longer palindrome found

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 and even length palindromes by expanding around single characters and between pairs

Summary

Finds the longest substring that reads the same forwards and backwards.

Use when you need to find the biggest palindrome inside a string.

Check palindromes by expanding around each character and between pairs to cover all cases.

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