Solution: Remove Palindromic Subsequences

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1332 (Easy): Remove Palindromic Subsequences

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

---

Examples:

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'

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The trick to this problem is realizing that since we're dealing with subsequences and only 2 possible characters, the answer cannot possible be larger than 2. In fact, the answer will always be 2 unless S is already a palindrome, in which case the answer is 1, or S is an empty string, in which case the answer is 0.

It's important to understand the distinction between a substring and a subsequence. A substring is a contiguous block of characters between one index and and another in the input string. A subsequence, which we're dealing with here, is any sequence of characters from the string, as long as they're in their original order. But you can pick and choose which characters you want in a subsequence, even if there are gaps between.

So in this situation I could, for example, create a subsequence of every single 'a' in the string. A string of all 'a' s would naturally be palindromic, so it could be removed from the original string. Since there are only 'a' s and 'b' s, that would leave only 'b' s remaining in the original string, which could be then removed in a second operation.

  S = "bbaabaaa"             // Input string
         ^^ ^^^              // Characters for the first subsequence
sub = "  aa aaa" = "aaaaa"   // Palindromic, so it can be removed
  S = "bb  b   " = "bbb"     // Remaining string is palindromic and can be removed

---

Implementation:

Python can more easily just compare the string with its reverse self via index access shorthand.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var removePalindromeSub = function(S) {
    if (!S) return 0
    for (let i = 0, j = S.length - 1; i < j; i++, j--)
        if (S.charAt(i) !== S.charAt(j)) return 2
    return 1
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def removePalindromeSub(self, S: str) -> int:
        if not S: return 0
        return 1 if S == S[::-1] else 2

---

Java Code:

(Jump to: Problem Description || Solution Idea)

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

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int removePalindromeSub(string S) {
        if (S == "") return 0;
        for (int i = 0, j = S.size() - 1; i < j; i++, j--)
            if (S[i] != S[j]) return 2;
        return 1;
    }
};