Longest Palindromic Substring in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of expanding around center approach

What is the output of the following Rust code that finds the longest palindromic substring by expanding around each center?

DSA Rust

fn longest_palindrome(s: &str) -> String {
    let chars: Vec<char> = s.chars().collect();
    let mut start = 0;
    let mut end = 0;
    
    for i in 0..chars.len() {
        let len1 = expand_around_center(&chars, i, i);
        let len2 = expand_around_center(&chars, i, i + 1);
        let len = len1.max(len2);
        if len > end - start {
            start = i.saturating_sub((len - 1) / 2);
            end = i + len / 2;
        }
    }
    chars[start..=end].iter().collect()
}

fn expand_around_center(chars: &[char], mut left: usize, mut right: usize) -> usize {
    while left <= right && right < chars.len() && chars[left] == chars[right] {
        if left == 0 { break; }
        left -= 1;
        right += 1;
    }
    right - left - 1
}

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

A "babad"

B "aba"

C "bad"

D "bab"

💡 Hint

Check how the function expands around each center and picks the longest palindrome.

The code expands around each character and between characters to find palindromes. For input "babad", both "bab" and "aba" are valid longest palindromes of length 3. However, the code picks the first longest palindrome it finds, which is "bab".

❓ Predict Output

intermediate

Output of dynamic programming approach

What is the output of this Rust code using dynamic programming to find the longest palindromic substring?

DSA Rust

fn longest_palindrome(s: &str) -> String {
    let n = s.len();
    if n == 0 { return String::new(); }
    let chars: Vec<char> = s.chars().collect();
    let mut dp = vec![vec![false; n]; n];
    let mut start = 0;
    let mut max_len = 1;

    for i in 0..n {
        dp[i][i] = true;
    }

    for length in 2..=n {
        for i in 0..=n - length {
            let j = i + length - 1;
            if chars[i] == chars[j] {
                if length == 2 || dp[i + 1][j - 1] {
                    dp[i][j] = true;
                    if length > max_len {
                        start = i;
                        max_len = length;
                    }
                }
            }
        }
    }
    chars[start..start + max_len].iter().collect()
}

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

A "cbbd"

B "bb"

C "b"

D "c"

💡 Hint

Look for the longest substring where dp[i][j] is true.

The dynamic programming table marks substrings that are palindromes. For input "cbbd", the longest palindrome substring is "bb".

🔧 Debug

advanced

Identify the error in Manacher's algorithm implementation

What error does the following Rust code produce when trying to find the longest palindromic substring using Manacher's algorithm?

DSA Rust

fn manacher(s: &str) -> String {
    let t: Vec<char> = s.chars().flat_map(|c| vec!['#', c]).chain(std::iter::once('#')).collect();
    let n = t.len();
    let mut p = vec![0; n];
    let mut center = 0;
    let mut right = 0;
    let mut max_len = 0;
    let mut max_center = 0;

    for i in 0..n {
        let mirror = 2 * center as isize - i as isize;
        if i < right {
            p[i] = p[mirror as usize].min(right - i);
        }
        while i + p[i] + 1 < n && i >= p[i] + 1 && t[i + p[i] + 1] == t[i - p[i] - 1] {
            p[i] += 1;
        }
        if i + p[i] > right {
            center = i;
            right = i + p[i];
        }
        if p[i] > max_len {
            max_len = p[i];
            max_center = i;
        }
    }

    let start = (max_center - max_len) / 2;
    s.chars().skip(start).take(max_len).collect()
}

fn main() {
    let input = "abacdfgdcaba";
    let result = manacher(input);
    println!("{}", result);
}

A Index out of bounds panic at line with while loop condition

B Compilation error due to missing semicolon

C Returns empty string for all inputs

D Infinite loop in while condition

💡 Hint

Check the boundary conditions in the while loop.

The while loop checks indices i + p[i] + 1 and i - p[i] - 1 without ensuring they are within bounds, causing an index out of bounds panic.

🧠 Conceptual

advanced

Time complexity of longest palindromic substring algorithms

Which of the following statements correctly describes the time complexity of common algorithms for finding the longest palindromic substring?

A Expand around center approach runs in O(n^2), Manacher's algorithm runs in O(n), dynamic programming runs in O(n^2)

B Expand around center approach runs in O(n), Manacher's algorithm runs in O(n^2), dynamic programming runs in O(n^3)

C All three algorithms run in O(n^3) time

D Dynamic programming runs in O(n), Manacher's algorithm runs in O(n^2), expand around center runs in O(n^2)

💡 Hint

Consider how many times each algorithm checks substrings.

Expand around center checks each center and expands, resulting in O(n^2). Manacher's algorithm uses clever preprocessing to achieve O(n). Dynamic programming fills an n x n table, also O(n^2).

🚀 Application

expert

Longest palindromic substring in streaming data

You receive a stream of characters one by one and want to find the longest palindromic substring seen so far at any point. Which data structure or algorithm approach is best suited for this problem?

A Store all substrings and check each for palindrome after each new character

B Use Manacher's algorithm on the entire string after each new character arrives

C Maintain a suffix tree or suffix automaton to track palindromic substrings efficiently

D Use a rolling hash with binary search to check palindromes on the fly

💡 Hint

Consider data structures designed for substring queries in streaming or online scenarios.

Suffix trees or suffix automatons can be adapted to track palindromic substrings efficiently in streaming data. Manacher's algorithm requires full string and is not online. Rolling hash with binary search is possible but less efficient. Storing all substrings is too slow.

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