1332. Remove Palindromic Subsequences #

Problem #

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’

Problem Summary #

Given a string s consisting only of the letters ‘a’ and ‘b’. In each deletion operation, you can remove one palindromic subsequence from s. Return the minimum number of deletions required to remove all characters from the given string (make the string empty).

Definition of “subsequence”: If a string can be obtained by deleting some characters from the original string without changing the order of the remaining characters, then this string is a subsequence of the original string.

Definition of “palindrome”: If a string reads the same backward as forward, then the string is a palindrome.

Solution Approach #

• After reading the problem, I thought it was an enhanced version of Problem 5. Each time, find the longest palindromic substring in the string and delete it, and keep deleting until no palindromic substring can be found. The total number of deletions + the number of remaining letters = the minimum number of deletions. After submitting, I got wrong answer, with an error on the test case bbaabaaa. If following the idea of finding the longest palindromic string, first find the longest palindromic substring aabaa; the remaining string is bba, which still needs 2 more deletions, bb and a. The total number of deletions is 3. Why was it wrong? Reading the problem carefully again, it says subsequence, which is not necessarily contiguous. Together with the fact that this problem is easy difficulty, it is actually very simple.
• The answer to this problem can only be 0, 1, or 2. The empty string corresponds to 0. If there is one letter, a single letter can form a palindrome, so the answer is 1. If the string length is at least 2, that is, both a and b exist, first delete all as, because all the as form a palindromic subsequence. Then delete all the bs, because all the bs form a palindromic subsequence. After these two steps, all characters can definitely be deleted.

Code #

package leetcode

func removePalindromeSub(s string) int {
	if len(s) == 0 {
		return 0
	}
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-1-i] {
			return 2
		}
	}
	return 1
}