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

Recall & Review

beginner

What is a palindrome?

A palindrome is a word, phrase, 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 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 time complexity of the expand-around-center approach for this problem?

O(n²), where n is the length of the string, because we check palindromes centered at each character and between characters.

intermediate

Why is dynamic programming used in the Longest Palindromic Substring problem?

Because it stores results of smaller palindrome checks to avoid repeated work, improving efficiency.

What is the simplest way to check if a substring is a palindrome?

A Reverse the substring and compare with original

B Compare characters from both ends moving inward

C Sort the substring and check equality

D Count vowels in the substring

Checking characters from both ends moving inward ensures palindrome property.

Which approach expands around centers to find palindromes?

A Expand Around Center

B Dynamic Programming

C Divide and Conquer

D Greedy

Expand Around Center checks palindromes by expanding from each character or pair.

What is the worst-case time complexity of the brute force method for this problem?

A O(n³)

B O(n)

C O(n²)

D O(log n)

Brute force checks all substrings (O(n²)) and palindrome check per substring (O(n)) leading to O(n³).

In dynamic programming for this problem, what does the DP table store?

A Number of vowels in substring s[i..j]

B Length of substring s[i..j]

C Whether substring s[i..j] is a palindrome

D Index of first character

DP table stores true/false if substring s[i..j] is palindrome.

Which of these is NOT a valid palindrome?

A a

B racecar

C madam

D hello

"hello" is not the same backward and forward.

Explain how the expand-around-center method finds the longest palindromic substring.

Think of checking palindromes by growing outwards from the middle.

Describe how dynamic programming helps optimize finding the longest palindromic substring.

Remember storing results to reuse them.