1332. Remove Palindromic Subsequences

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.

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: String is already palindrome

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”.

Example 4:
Input: s = “”
Output: 0

Constraints:
0 <= s.length <= 1000
s only consists of letters ‘a’ and ‘b’

Solution:
subsequence vs. subarray

• subsquence does not have to be consecutive
• subarray need to be consecutive
  Two base cases
• empty string return 0
• already palindromic string return 1
  if not two base cases, then at least two steps
• remove all “a”
• remove all “b”
• since subsequences are composed of only one type of letter always palindrome strings

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int removePalindromeSub(String s) {
        // ArrayList<String> myList = new ArrayList<String>(Arrays.asList(s.split("")));
        // return s.isEmpty() ? 0 : (checkPalindromic(myList) ? 1:2);
        return s.isEmpty() ? 0 : (s.equals(new StringBuilder(s).reverse().toString()) ? 1:2);
    }
    public boolean checkPalindromic(ArrayList myList) {
        int len = myList.size();
        int j = len - 1;
        for (int i=0; i<len/2; i++) {
            if (myList.get(i).equals(myList.get(j))) {
                j--;
            } else {
                return false;
            }
        }
        return true;
    }
}

Python

1
2
3

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

references

• https://leetcode.com/problems/remove-palindromic-subsequences/