Remove Palindromic Subsequences (LeetCode 1332): The Answer Is Never More Than Two

The string contains only a and b. In one step you may delete any palindromic subsequence. Return the minimum number of steps to empty the string.

The trick in the wording

A subsequence does not have to be contiguous. All the a's together form a palindrome, and so do all the b's. So two steps always suffice. If the whole string is already a palindrome, one step is enough. An empty string needs zero.

def remove_palindrome_sub(s):
    if not s:
        return 0
    return 1 if s == s[::-1] else 2

How to present it

Many candidates start writing a DP. Pause and ask what subsequence means here; spotting that the alphabet has two letters turns the problem into a palindrome check. Interviewers like hearing that reasoning before any code.

For more practice reading problem statements carefully under time pressure, try this AI help for online coding assessments.

Disclosure: I work on Linkjob AI.