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.
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
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.