Watch 10 video solutions for Remove Palindromic Subsequences, a easy level problem involving Two Pointers, String. This walkthrough by Fraz has 12,195 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.
A string is called palindrome if is one that reads the same backward as well as forward.
Example 1:
Input: s = "ababa" Output: 1 Explanation: s is already a palindrome, so its entirety can be removed in a single 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 <= 1000s[i] is either 'a' or 'b'.Problem Overview: You are given a string s containing only the characters 'a' and 'b'. In one operation, you can remove any subsequence that forms a palindrome. The task is to return the minimum number of operations required to delete the entire string.
Approach 1: Check If String is a Palindrome (O(n) time, O(1) space)
The key observation: because the string contains only two characters (a and b), the answer can never exceed 2. If the entire string is already a palindrome, you can remove it in one operation. Otherwise, remove all a characters in one step and all b characters in another. To verify the first case, use the two pointers technique—place one pointer at the start and one at the end, then move inward while comparing characters. If every pair matches, the string is a palindrome and the answer is 1. If any mismatch appears, the answer must be 2.
This works because any sequence of identical characters is itself a palindrome. Even if the full string is not symmetric, removing all as forms one palindromic subsequence and removing all bs forms another. The check itself is linear since each character is visited once.
Approach 2: Count Unique Characters and Remove (O(n) time, O(1) space)
Another way to reason about the problem is by counting distinct characters in the string. Since subsequences do not need to be contiguous, all occurrences of the same character can be removed together as a palindrome (for example, "aaaa"). Scan the string and track the set of unique characters using simple frequency checks. If only one character appears, the whole string is already a palindrome and can be removed in one operation.
If two characters exist (a and b), you can always remove them in exactly two steps: remove the subsequence containing all as, then remove all bs. This approach treats the problem as a property of the string composition rather than checking symmetry. The scan is linear and uses constant extra memory.
Recommended for interviews: The palindrome check using two pointers is usually expected. It shows you recognize the constraint that the answer is at most two and can verify the palindrome condition efficiently. The character-count reasoning is equally valid but the two-pointer explanation demonstrates stronger familiarity with common two pointer patterns used in string problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Check if Entire String is Palindrome (Two Pointers) | O(n) | O(1) | Best general solution. Quickly determines if the whole string can be removed in one step. |
| Count Unique Characters | O(n) | O(1) | Useful when reasoning about character composition rather than symmetry. |