Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Meta coding screen, just one problem about k-palindromes. Short session, not much to say beyond the problem itself.

Questions Asked (1)

Given a string, determine whether it can be made into a palindrome by removing at most K characters.

Algorithms & Data Structures

Author's notes

Classic edit-distance variant but I kept second-guessing whether to go DP straight away or try the two-pointer shortcut first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the minimum number of deletions to make a string a palindrome, which equals n minus the length of the longest palindromic subsequence (LPS). Then check if that minimum is ≤ K. Use dynamic programming to compute the LPS length in O(n^2) time and O(n) space.

Pro tip: Clarify that 'removing at most K characters' means we can delete any characters, not just from the ends. Also, mention that if K ≥ n-1, the answer is always true, and handle edge cases like empty strings.

1. Clarify the problem

Confirm that removal can be from anywhere, and that we need to check if the minimum deletions ≤ K. Discuss edge cases (empty string, K ≥ n-1).

2. Relate to longest palindromic subsequence

Explain that the minimum deletions to make a palindrome equals n minus the length of the longest palindromic subsequence (LPS). So the condition is n - LPS ≤ K.

3. Design DP for LPS

Define dp[i][j] as the LPS length of substring s[i..j]. Recurrence: 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]). Base cases: dp[i][i] = 1, dp[i][i-1] = 0.

4. Optimize space

Since dp[i][j] depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1], we can reduce space to O(n) by iterating i from n-1 down to 0 and j from i+1 to n-1, keeping only two rows or a 1D array with careful updates.

5. Analyze complexity and conclude

Time complexity O(n^2), space O(n). Compare n - LPS with K and return true if ≤ K. Discuss potential follow-ups like if K is small, we might use a different approach.

Key Points to Mention

Minimum deletions = n - length of longest palindromic subsequence (LPS).
Dynamic programming recurrence for LPS: dp[i][j] = dp[i+1][j-1] + 2 if s[i]==s[j], else max(dp[i+1][j], dp[i][j-1]).
Space optimization from O(n^2) to O(n) by using a 1D array or two rows.
Edge cases: empty string, K ≥ n-1, and strings that are already palindromes.
Time complexity O(n^2) and space complexity O(n).
Alternative approach: two-pointer with recursion and memoization, but DP is more efficient.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.