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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the recurrence relation for Longest Palindromic Subsequence?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “LPS(i, j) = length of longest palindromic subsequence in s[i..j]. Base cases: LPS(i, i) = 1 (single character is a palindrome). LPS(i, i+1) = 2 if s[i] == s[i+1], else 1. Recurrence: if s[i] == s[j]: LPS(i, j) = LPS(i+1, j-1) + 2 (both end characters match — include them and add the LPS of the inner substring). If s[i] != s[j]: LPS(i, j) = max(LPS(i+1, j), LPS(i, j-1)) (skip either the left or right character — whichever gives the longer subsequence). Fill the table by increasing substring length (outer loop on length, inner on starting index). Result: LPS(0, n-1). Time O(n^2), Space O(n^2). Space optimization: only need the previous diagonal, reducible to O(n).”
}
},
{
“@type”: “Question”,
“name”: “How does the palindrome DP table work and how do you fill it correctly?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The 2D palindrome table: is_palindrome[i][j] = True if s[i..j] is a palindrome. Fill order matters: to compute dp[i][j], you need dp[i+1][j-1] — the answer for the inner substring. So you must fill shorter substrings before longer ones. Fill by increasing length: for length from 1 to n: for i from 0 to n-length: j = i + length – 1; if length == 1: dp[i][j] = True; elif length == 2: dp[i][j] = (s[i] == s[j]); else: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. This gives O(n^2) time and space. Alternative fill: iterate i from n-1 down to 0, j from i+1 to n-1. This fills the table from the bottom-right diagonal upward, which also ensures dp[i+1][j-1] is computed before dp[i][j].”
}
},
{
“@type”: “Question”,
“name”: “How do you solve Palindrome Partitioning with minimum cuts (LC 132)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “dp[i] = minimum cuts for s[0..i]. Initialize dp[i] = i (maximum cuts: each character is its own palindrome). For each i from 0 to n-1: if s[0..i] is a palindrome: dp[i] = 0 (no cuts needed). Else: for each j from 1 to i: if s[j..i] is a palindrome: dp[i] = min(dp[i], dp[j-1] + 1). This uses the precomputed is_palindrome table for O(1) palindrome checks. The nested loop is O(n^2) and each iteration is O(1), giving O(n^2) total. Return dp[n-1]. Alternative 1D approach: expand around each center and update dp values — same O(n^2) complexity but avoids the separate is_palindrome table. The key insight: every palindromic suffix ending at position i defines a valid cut point.”
}
},
{
“@type”: “Question”,
“name”: “What is Manacher’s algorithm and when do you need it in interviews?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Manacher’s algorithm finds the longest palindromic substring (and all palindrome radii) in O(n) time using the insight that palindromes can mirror each other. It maintains a rightmost palindrome boundary R and its center C. For each position i: if i is within the current rightmost palindrome, its palindrome radius is at least the mirror of i around C (use the smaller of the mirrored radius and the distance to R). Then try to extend further. When i falls outside R, expand from scratch. The algorithm never backtracks on the left side of R. For interviews: O(n^2) expand-around-center (21 lines of code) is what interviewers expect. Manacher’s is O(n) but 50+ lines of careful code — mention it exists for bonus points but implement the O(n^2) solution unless explicitly asked for O(n).”
}
},
{
“@type”: “Question”,
“name”: “What is the relationship between LPS and LCS?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “LPS(s) = LCS(s, reverse(s)). A palindromic subsequence of s is a subsequence that reads the same as its reverse. By reversing s and finding the LCS: any common subsequence of s and its reverse is a sequence that appears in s in forward order AND in reverse order simultaneously — meaning it reads the same both ways, which is the definition of a palindrome. This reduces LPS to LCS which has a well-known O(n^2) DP solution. Practical implication: you can code LPS using the LCS template with reverse(s) as the second string. However, the direct LPS DP (using the two-pointer recurrence) is slightly simpler to derive from first principles in an interview. The LCS-based reduction is useful for proving correctness or if you remember LCS better than LPS.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide