Palindrome Check
A palindrome reads the same forward and backward. Brute force check: O(n). Two-pointer: left=0, right=n-1; while left < right: if s[left] != s[right]: return False; left++, right–; return True. To check all substrings: precompute a 2D boolean table dp[i][j] = True if s[i:j+1] is a palindrome. Base cases: dp[i][i] = True (single char). dp[i][i+1] = (s[i] == s[i+1]). Transition (fill diagonally by length): dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1]. O(n^2) time and space.
Expand around center: for each center (both single characters and gaps between characters), expand outward while s[left] == s[right]. Total time O(n^2), space O(1) (no table). More efficient for “find all palindromic substrings.” Manacher’s algorithm: O(n) for all palindrome lengths. Rarely needed in interviews but good to know exists.
Longest Palindromic Subsequence (LC 516)
Find the length of the longest subsequence of s that is a palindrome. Note: subsequence, not substring (characters need not be contiguous). dp[i][j] = length of LPS in s[i:j+1]. Base: dp[i][i] = 1. Transition: if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2. Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Fill in increasing order of (j – i). O(n^2) time and space. Relationship: LPS(s) = LCS(s, reverse(s)) — the longest palindromic subsequence is the LCS of s with its reverse.
def lps(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n): dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = (dp[i+1][j-1] if length > 2 else 0) + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]Minimum Cuts for Palindrome Partitioning (LC 132)
Find the minimum number of cuts to partition s into palindromic substrings. dp[i] = minimum cuts for s[:i+1]. For each i: for each j from 0 to i: if s[j:i+1] is a palindrome: dp[i] = min(dp[i], dp[j-1] + 1). Use the precomputed is_palindrome table. O(n^2) time. Optimization: precompute is_palindrome using the expand-around-center technique in O(n^2).
Palindrome Partitioning II (All Partitions, LC 131)
Return all possible palindrome partitions of s. Backtracking: at each position, try all palindromic substrings starting here. If a substring s[start:end+1] is a palindrome: add to current partition, recurse from end+1. Base case: start == len(s) → add current partition to result. Use the precomputed is_palindrome table for O(1) palindrome checks during backtracking. Total time: O(n * 2^n) in the worst case (exponential output for all-same-character strings like “aaa…a”). The is_palindrome table precomputation is O(n^2).
Count Palindromic Substrings (LC 647)
Count the total number of palindromic substrings. Expand around center: for each of the 2n-1 centers (n single chars, n-1 gaps), expand while s[left] == s[right] and count. Total count += expansion steps + 1 (for the center itself). O(n^2) time, O(1) space. Alternatively: build the is_palindrome table in O(n^2) and sum True values. The expand-around-center approach is more elegant.
Longest Palindromic Substring (LC 5)
Find the longest palindromic substring (contiguous). Expand around center: track the maximum length and its start/end. Update when a longer palindrome is found. O(n^2) time, O(1) space. Manacher’s: O(n). For interview: O(n^2) expand-around-center is sufficient and easy to implement. O(n) Manacher’s is impressive but complex to code under pressure.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide