LeetCode 1332 - Remove Palindromic Subsequences

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

The problem gives us a string s that contains only the characters 'a' and 'b'. In one operation, we are allowed to remove any subsequence of the string, as long as that subsequence forms a palindrome.

A subsequence is different from a substring. A substring must be contiguous, but a subsequence can skip characters while preserving relative order. For example, in the string "baabb", the subsequence "baab" can be formed by taking characters at indices 0, 1, 2, 4.

The goal is to determine the minimum number of operations needed to completely remove the string.

The key detail is that we are removing palindromic subsequences, not palindromic substrings. This makes the problem much easier than it may initially appear.

The constraints are small, 1 <= s.length <= 1000, but the real insight is that the answer can only ever be 1 or 2.

If the entire string itself is already a palindrome, then we can remove it in a single operation.

If the string is not a palindrome, we can always remove all 'a' characters in one operation and all 'b' characters in another operation. Since a sequence consisting entirely of one repeated character is always a palindrome, both removals are valid.

This means:

If s is a palindrome, answer is 1
Otherwise, answer is 2

There is no case requiring more than two operations because the string contains only two distinct characters.

Some important edge cases include:

A single-character string such as "a" or "b", which is always a palindrome.
Strings with all identical characters such as "aaaa", which can be removed in one step.
Non-palindromic mixed strings such as "abb" or "baabb", which require two operations.
The problem guarantees the string is non-empty and contains only 'a' and 'b', so we do not need to handle invalid characters or empty input.

Approaches

Brute Force Approach

A brute-force solution would attempt to simulate the process of removing palindromic subsequences in all possible ways.

For every step, we could generate every possible subsequence of the current string, check whether it is a palindrome, remove it, and recursively compute the minimum remaining operations.

This approach is theoretically correct because it explores every valid removal sequence and eventually finds the optimal answer.

However, it is computationally infeasible. A string of length n has 2^n possible subsequences. Checking all subsequences recursively would lead to exponential time complexity, which becomes impractical even for relatively small values of n.

Although the constraint is only 1000, exponential algorithms are completely impossible at this scale.

Optimal Approach

The crucial observation is that the string contains only two characters: 'a' and 'b'.

If the string is already a palindrome, we can remove the entire string in one operation.

If it is not a palindrome, we can still always finish in two operations:

Remove all 'a' characters as one palindromic subsequence.
Remove all 'b' characters as another palindromic subsequence.

Any sequence made entirely of one repeated character is automatically a palindrome.

Therefore, the answer is never greater than 2.

The entire problem reduces to checking whether the string itself is a palindrome.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n) or worse	O(2^n)	Generates and tests all palindromic subsequences
Optimal	O(n)	O(1)	Check whether the string is a palindrome

Algorithm Walkthrough

Start with the input string s.
Check whether s reads the same forward and backward.

This can be done using two pointers:

One pointer starts at the beginning.
One pointer starts at the end.

At each step, compare the characters. 3. If every mirrored pair matches, then the string is a palindrome.

Since the whole string is itself a palindromic subsequence, we can remove it in one operation. 4. If any pair of characters does not match, then the string is not a palindrome.

In this situation, we know we can always:

Remove all 'a' characters in one operation.
Remove all 'b' characters in another operation.

Therefore, return 2.

Why it works

The correctness relies on two facts:

Any string consisting of identical characters is a palindrome.
The input contains only 'a' and 'b'.

If the full string is a palindrome, one operation is sufficient.

Otherwise, all 'a' characters form one palindromic subsequence and all 'b' characters form another. Removing both guarantees the string becomes empty in at most two operations.

Since one operation is impossible for a non-palindromic string, the minimum must be exactly 2.

Python Solution

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        left = 0
        right = len(s) - 1

        while left < right:
            if s[left] != s[right]:
                return 2

            left += 1
            right -= 1

        return 1

The implementation uses the classic two-pointer palindrome check.

The left pointer starts at the beginning of the string, while the right pointer starts at the end.

During each iteration, the algorithm compares the characters at these positions. If they differ, the string is not a palindrome, so the answer must be 2.

If the loop completes without finding a mismatch, the string is a palindrome, so the answer is 1.

The solution avoids extra memory allocation and runs in linear time.

Go Solution

func removePalindromeSub(s string) int {
    left := 0
    right := len(s) - 1

    for left < right {
        if s[left] != s[right] {
            return 2
        }

        left++
        right--
    }

    return 1
}

The Go implementation follows the same logic as the Python version.

Strings in Go can be indexed directly using s[i], which returns a byte. Since the input contains only ASCII characters 'a' and 'b', byte indexing is perfectly safe.

No additional slices or memory allocations are required, so the implementation remains constant in space usage.

Worked Examples

Example 1

Input:

s = "ababa"

Palindrome check:

Left Index	Right Index	Left Char	Right Char	Match
0	4	a	a	Yes
1	3	b	b	Yes

The pointers cross without mismatches.

The string is a palindrome, so the answer is:

Example 2

Input:

s = "abb"

Palindrome check:

Left Index	Right Index	Left Char	Right Char	Match
0	2	a	b	No

A mismatch is found immediately.

The string is not a palindrome.

We can remove:

"a" in one operation
"bb" in another operation

Answer:

Example 3

Input:

s = "baabb"

Palindrome check:

Left Index	Right Index	Left Char	Right Char	Match
0	4	b	b	Yes
1	3	a	b	No

The second comparison fails.

The string is not a palindrome.

One valid removal sequence is:

"baabb"
-> remove "baab"
-> "b"
-> remove "b"
-> ""

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is checked at most once
Space	O(1)	Only a few pointer variables are used

The algorithm performs a single pass from both ends of the string toward the center. Since each comparison processes one pair of characters, the total work is proportional to the length of the string.

No auxiliary data structures are required, so the space usage remains constant.

Test Cases

solution = Solution()

assert solution.removePalindromeSub("ababa") == 1  # already a palindrome
assert solution.removePalindromeSub("abb") == 2  # simple non-palindrome
assert solution.removePalindromeSub("baabb") == 2  # mixed characters

assert solution.removePalindromeSub("a") == 1  # single character
assert solution.removePalindromeSub("b") == 1  # single character

assert solution.removePalindromeSub("aa") == 1  # repeated same character
assert solution.removePalindromeSub("bbbbbb") == 1  # all same character

assert solution.removePalindromeSub("ab") == 2  # smallest non-palindrome
assert solution.removePalindromeSub("abab") == 2  # alternating non-palindrome

assert solution.removePalindromeSub("abba") == 1  # even-length palindrome
assert solution.removePalindromeSub("babab") == 1  # odd-length palindrome

assert solution.removePalindromeSub("aababb") == 2  # longer non-palindrome

Test	Why
`"ababa"`	Validates already-palindromic input
`"abb"`	Tests immediate mismatch
`"baabb"`	Tests mismatch after several comparisons
`"a"`	Smallest valid input
`"b"`	Single-character edge case
`"aa"`	All identical characters
`"bbbbbb"`	Larger repeated-character palindrome
`"ab"`	Smallest non-palindrome
`"abab"`	Alternating pattern
`"abba"`	Even-length palindrome
`"babab"`	Odd-length palindrome
`"aababb"`	General non-palindromic mixed string

Edge Cases

Single Character Strings

A string containing only one character is always a palindrome because it reads the same forward and backward.

Examples include "a" and "b".

This case can sometimes cause off-by-one errors in two-pointer implementations, especially when the pointers start equal. The implementation handles this correctly because the loop condition is left < right. For a single-character string, the loop never runs, and the function correctly returns 1.

Strings With All Identical Characters

Strings such as "aaaa" or "bbbbbb" are palindromes because every mirrored character pair matches.

A naive solution might overcomplicate the problem and attempt unnecessary removals. The palindrome check immediately recognizes these strings and returns 1.

Non-Palindromic Strings

Strings like "ab" or "abb" are not palindromes.

The important observation is that they still never require more than two operations. Since the input only contains 'a' and 'b', we can always remove all occurrences of one character first, then remove all occurrences of the other character.

The implementation correctly returns 2 as soon as it detects the first mismatch during the palindrome check.