Skip to main content

1332 - Remove Palindromic Subsequences

Difficulty: Easy | Pattern: String Analysis | Company tags: Amazon

Problem Statement​

You are given a string s consisting only of letters 'a' and 'b'. In one step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

Note: A subsequence is a sequence derivable from another sequence by deleting some or no elements without changing the order of remaining elements. A string is palindromic if it equals its reverse.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so remove it in one step.

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" → remove "bb" (step 1) → "a" (step 2)

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" → remove "bab" or "baa...b" palindrome, then remove remainder.

Key Insight: Answer is Always 0, 1, or 2​

Since s only contains 'a' and 'b':

  1. 0 steps: If s = "" → already empty.
  2. 1 step: If s is a palindrome → remove the whole string in one step (any string is a subsequence of itself, and the whole string is a valid palindromic subsequence if it's a palindrome).
  3. 2 steps: If s is not a palindrome → remove all 'a's (always a palindromic subsequence of all 'a's) in step 1, then all 'b's (palindromic) in step 2.
def removePalindromeSub(s: str) -> int:
    if not s:
        return 0
    if s == s[::-1]:
        return 1
    return 2

Algorithm Flow​

Why This Works​

The only characters are 'a' and 'b'. Any sequence of all 'a's is a palindrome, and any sequence of all 'b's is a palindrome. So in at most 2 steps, we can always empty the string.

We can NEVER need more than 2 steps for a string of only two characters.

Dry Run​

  • s = "ababa": reversed = "ababa" = same → palindrome → 1
  • s = "abb": reversed = "bba" ≠ "abb" → not palindrome → 2
  • s = "": empty → 0
  • s = "b": palindrome → 1

Edge Cases​

  • Empty string → 0
  • Single character → always palindrome → 1
  • All same character → palindrome → 1

Complexity​

  • Time: O(n) — palindrome check
  • Space: O(n) — reversed string

Key Terms​

TermDefinition
Palindromic subsequenceA subsequence (not necessarily contiguous) that reads the same forwards and backwards.
SubsequenceA sequence derived by deleting zero or more characters without reordering the rest.
Binary-alphabet trickConstraint that the string uses only 2 distinct characters, bounding the answer to a small constant.
Constructive proofShowing an answer is achievable by explicitly building a solution, rather than searching for one.

FAQ​

Q1: Why is the answer never more than 2? Because with only two characters ('a' and 'b'), any maximal run of a single character is itself a palindrome, so removing all 'a's and then all 'b's always empties the string in 2 steps.

Q2: Can the greedy check s == s[::-1] ever give a false positive? No — if s equals its own reverse, s is by definition a palindrome, and a string is always a subsequence of itself, so it can be removed in one step.

Q3: Does this approach work if the string contains 3 or more distinct characters? No. The O(1)-step bound relies on only 2 characters existing. With 3+ characters, the problem becomes substantially harder (related to palindrome partitioning) and this trick doesn't apply.

Q4: What's the time complexity of the reverse-and-compare check? O(n) to reverse the string and O(n) to compare, so O(n) overall — dominated by a single linear pass.

Q5: Is there a way to solve this without reversing the string? Yes — use a two-pointer check (i from the start, j from the end, compare s[i] == s[j]) to test the palindrome property in O(n) time and O(1) extra space, avoiding the O(n) space of s[::-1].

Quick Revision​

  • Alphabet is restricted to 'a' and 'b' only — this is the key constraint that bounds the answer.
  • Answer is always 0, 1, or 2 — never more.
  • 0 steps: string is already empty.
  • 1 step: string equals its own reverse (it's a palindrome).
  • 2 steps: not a palindrome → remove all 'a's (palindrome), then all 'b's (palindrome).
  • No DP or backtracking needed — this is a constant-time-answer, O(n)-check problem.
  • Two-pointer comparison avoids the O(n) space cost of slicing s[::-1].
  • Classic "trick question" pattern: look for a hidden constraint (small alphabet) that collapses complexity.
  • 125 - Valid Palindrome — same reverse/two-pointer palindrome check.
  • 5 - Longest Palindromic Substring — shares the palindrome-detection core, but without the small-alphabet shortcut.
  • Pattern: "trick constraint" problems where a small input alphabet or limited value range bounds the answer to a small constant.