Longest Palindromic Substring in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a palindrome?

A palindrome is a word, phrase, number, or sequence that reads the same backward as forward, like 'madam' or 'racecar'.

beginner

What does the 'Longest Palindromic Substring' problem ask for?

It asks to find the longest continuous part (substring) of a string that is a palindrome.

beginner

How can you check if a substring is a palindrome?

By comparing characters from the start and end moving towards the center, ensuring they match.

intermediate

What is the center expansion technique in finding palindromes?

It means starting from a center point and expanding outwards to check for palindromes around that center.

intermediate

Why do we consider both odd and even length centers in palindrome search?

Because palindromes can have a single center character (odd length) or two center characters (even length), so both cases must be checked.

What is the time complexity of the naive approach to find the longest palindromic substring by checking all substrings?

A O(n^3)

B O(n^2)

C O(n)

D O(log n)

The naive approach checks all substrings (O(n^2)) and each substring palindrome check takes O(n), so total O(n^3).

In the center expansion method, how many centers do we consider for a string of length n?

A n^2

B n

C 2n - 1

D n/2

We consider n centers for odd length palindromes and n-1 centers for even length palindromes, total 2n - 1.

Which data structure is primarily used to store the longest palindromic substring during the algorithm?

A Stack

B Queue

C Hash Map

D String variables or indices

We keep track of start and end indices or the substring itself as a string variable.

What is the output of the longest palindromic substring algorithm for input 'babad'?

A bab

B bab or aba

C aba

D bad

Both 'bab' and 'aba' are valid longest palindromic substrings of length 3.

Which approach is more efficient for longest palindromic substring: dynamic programming or center expansion?

A Center expansion with O(n^2) time and O(1) space

B Sorting the string

C Naive approach with O(n^3) time

D Dynamic programming with O(n^2) time and space

Center expansion uses O(n^2) time but only O(1) space, making it more space efficient than DP.

Explain how the center expansion technique works to find the longest palindromic substring.

Think about starting from the middle and moving left and right.

Describe why we need to check both odd and even length palindromes separately.

Consider palindromes like 'aba' and 'abba'.