Remove Palindromic Subsequences

Difficulty: Easy | Acceptance: 77.00% | Paid: No Topics: Two Pointers, String

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

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

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

• Examples
• Constraints
• Direct Check Approach
• Two Pointers Approach
• Built-in Reverse Approach

Examples

Example 1:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so we can remove the entire string in one step.

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "".
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "".
Remove palindromic subsequence "baab" then "b".

Constraints

1 <= s.length <= 1000
s[i] is either 'a' or 'b'.

Direct Check

Intuition Since the string only contains ‘a’ and ‘b’, we can always remove all ‘a’s (a palindrome subsequence) in one step and all ‘b’s in another step. If the entire string is already a palindrome, we can remove it in one step.

Steps

• If the string is empty, return 0
• If the string is a palindrome, return 1
• Otherwise, return 2 (remove all ‘a’s, then all ‘b’s)

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        if s == s[::-1]:
            return 1
        return 2

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) for the two-pointer approach, O(n) for Python’s string reversal
• Notes: The Python solution uses string reversal which creates a new string, while other languages use two pointers for O(1) space.

Two Pointers

Intuition Use two pointers starting from both ends of the string to check if it’s a palindrome without creating a reversed copy.

Steps

• If the string is empty, return 0
• Use two pointers (left and right) to check if the string is a palindrome
• If all characters match, return 1
• Otherwise, return 2

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return 2
            left += 1
            right -= 1
        return 1

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1)
• Notes: This approach uses constant space by comparing characters in place.

Built-in Reverse

Intuition Leverage built-in string reversal functions to check for palindromes by comparing the string with its reverse.

Steps

• If the string is empty, return 0
• Compare the string with its reversed version
• If they match, return 1
• Otherwise, return 2

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        return 1 if s == s[::-1] else 2

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for storing the reversed string
• Notes: This approach is concise but uses O(n) extra space for the reversed string.