Remove Palindromic Subsequences

EASY

Description

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 <= 1000
s[i] is either 'a' or 'b'.

Approaches

Checkout 2 different approaches to solve Remove Palindromic Subsequences. Click on different approaches to view the approach and algorithm in detail.

Palindrome Check via String Reversal

This approach hinges on the key observation that the problem can be simplified to determining if the input string is a palindrome. The string s consists only of 'a's and 'b's.

If s is already a palindrome, it can be removed in one step.
If s is not a palindrome, we can always remove all occurrences of 'a' as one palindromic subsequence, and then all occurrences of 'b' as a second palindromic subsequence. This is because a sequence of identical characters (like "aaaa" or "bbb") is always a palindrome. Therefore, any non-palindromic string can be cleared in exactly two steps.

This approach checks if the string is a palindrome by creating a reversed copy of the string and comparing it to the original.

Algorithm

Check if the input string s is empty. If so, return 0.
Create a new string by reversing s.
Compare the original string s with the reversed string.
If they are identical, s is a palindrome. Return 1.
Otherwise, s is not a palindrome. Return 2.

The algorithm first handles the edge case of an empty string, which requires 0 steps. For non-empty strings, it creates a new string that is the reverse of the input string s. It then compares this new reversed string with the original string s. If they are equal, it means s is a palindrome, and the answer is 1. If they are not equal, s is not a palindrome, and based on our core logic, the answer is 2.

class Solution {
    public int removePalindromeSub(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        String reversedS = new StringBuilder(s).reverse().toString();
        if (s.equals(reversedS)) {
            return 1;
        } else {
            return 2;
        }
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the string. Creating the reversed string using `StringBuilder` takes O(N) time, and comparing the two strings also takes O(N) time.Space Complexity: O(N), as it requires extra space to store the reversed copy of the string.

Pros and Cons

Pros:

Simple to understand and implement using built-in string manipulation functions.

Cons:

Uses extra space that is proportional to the input string's length, which is less efficient than an in-place check.

Code Solutions

Checking out 3 solutions in different languages for Remove Palindromic Subsequences. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Remove Palindromic Subsequences

Patterns:

Two Pointers

Data Structures:

String