Remove Palindromic Subsequences

easy string two pointers palindrome

Problem

You are given a string s built only from the letters 'a' and 'b'. In one move you may pick any palindromic subsequence of s (characters keep their order but need not be adjacent, and must read the same forwards and backwards) and delete all of its characters at once. Return the minimum number of moves needed to make s empty.

Constraints: 1 ≤ s.length ≤ 1000 and every character is 'a' or 'b' — the two-letter alphabet is the key restriction.

Inputs = "baabb"

Output2

"baabb" is not a palindrome, so one move cannot take everything; deleting the subsequence "aa" leaves "bbb", a palindrome removed in a second move.

s (only letters 'a' and 'b', max 16)

def remove_palindrome_sub(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return 2
        i += 1
        j -= 1
    return 1

function removePalindromeSub(s) {
  let i = 0, j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return 2;
    i++;
    j--;
  }
  return 1;
}

int removePalindromeSub(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return 2;
        i++;
        j--;
    }
    return 1;
}

int removePalindromeSub(string s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return 2;
        i++;
        j--;
    }
    return 1;
}

Explanation

The trap is reading subsequence as substring. A subsequence may skip characters, and because s contains only 'a' and 'b', the set of all 'a's is automatically a palindromic subsequence (identical letters read the same both ways), and so is the set of all 'b's. Deleting one set and then the other empties any input — so the answer is never more than 2.

When is one move enough? Exactly when s is itself a palindrome, since the whole string is a subsequence of itself and can be deleted in a single move. The answer is never 0 because the string is non-empty. The whole problem therefore collapses to a single palindrome check.

We check with two pointers: i starts at the front, j at the back. While i < j, compare s[i] and s[j]. Any mismatch proves s is not a palindrome and we return 2 immediately; on a match both pointers move inward. If they meet or cross without a mismatch, return 1.

Default example s = "baabb": s[0]='b' matches s[4]='b', so the pointers move inward. Then s[1]='a' differs from s[3]='b' — not a palindrome, answer 2. Concretely: remove the palindromic subsequence "aa", leaving "bbb", then remove "bbb".

Each pointer only moves inward, so at most n/2 comparisons happen: O(n) time. We store nothing but the two indices: O(1) extra space.

Time: O(n) Space: O(1)