How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Decide palindrome within k deletions

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Decide palindrome within k deletions states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a string s and integer k, decide whether s can be transformed into a palindrome by deleting at most k characters. Provide an algorithm to compute the minimum number of deletions required to make s a palindrome and compare it with k. Discuss a DP solution and its time/space trade-offs, and outline optimizations for large inputs.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Decide palindrome within k deletions states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a string `s` and an integer `k`, determine whether `s` can be transformed into a palindrome by deleting **at most `k`** characters. The minimum number of deletions required to make a string a palindrome equals `n - L`, where `n = len(s)` and `L` is the length of the longest palindromic subsequence (LPS) of `s` (each character not in the LPS must be deleted). Return `True` if this minimum is `<= k`, otherwise `False`. **Examples** - `s = "abcdeca", k = 2` -> `True`. The LPS is `"aceca"` (length 5), so minimum deletions = 7 - 5 = 2, which is `<= 2`. - `s = "aebcbda", k = 1` -> `False`. The LPS is `"abcba"` (length 5), so minimum deletions = 7 - 5 = 2, which is `> 1`. - `s = "abca", k = 1` -> `True`. Deleting one of `b`/`c` yields `"aba"`/`"aca"`, so minimum deletions = 1 `<= 1`.

Constraints

0 <= len(s) <= 1000
0 <= k <= len(s)
s consists of lowercase English letters

Examples

Input: ("abcde", 1)

Expected Output: False

Explanation: LPS length is 1 (any single char), so min deletions = 5 - 1 = 4 > 1.

Input: ("abca", 1)

Expected Output: True

Explanation: LPS is 'aba' or 'aca' (length 3), min deletions = 4 - 3 = 1 <= 1.

Input: ("abcdeca", 2)

Expected Output: True

Explanation: LPS is 'aceca' (length 5), min deletions = 7 - 5 = 2 <= 2.

Input: ("", 0)

Expected Output: True

Explanation: Empty string is already a palindrome; 0 deletions needed.

Input: ("a", 0)

Expected Output: True

Explanation: A single character is a palindrome; 0 deletions needed.

Input: ("ab", 0)

Expected Output: False

Explanation: LPS length 1, min deletions = 2 - 1 = 1 > 0.

Input: ("aebcbda", 1)

Expected Output: False

Explanation: LPS is 'abcba' (length 5), min deletions = 7 - 5 = 2 > 1.

Input: ("racecar", 0)

Expected Output: True

Explanation: Already a palindrome; min deletions = 0 <= 0.

Hints

The minimum deletions to make s a palindrome is n minus the length of its longest palindromic subsequence (LPS).
Compute the LPS with interval DP: dp[i][j] is the LPS length within s[i..j]. If s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
Once you have min_deletions = n - LPS, the answer is simply min_deletions <= k. For large inputs, collapse the 2D table to two rolling rows for O(n) space.

Quick Overview