1332. Remove Palindromic Subsequences Leetcode Easy

PROBLEM STATEMENT

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.

TEST CASES

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

IDEA

Before getting on to the main problem, lets understand what is a subsequence and what is a substring.

Subsequence - A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.
For the same example, there are 15 sub-sequences. They are (1), (2), (3), (4), (1,2), (1,3),(1,4), (2,3), (2,4), (3,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4). More generally, we can say that for a sequence of size n, we can have (2^n-1) non-empty sub-sequences in total.
Substring - A subbarray is a contiguous part of array. An array that is inside another array. For example, consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays. The subbarays are (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3,4) and (1,2,3,4). In general, for an array/string of size n, there are n*(n+1)/2 non-empty subarrays/subsrings.

So now coming to our problem, we need to remove palindromic subsequence to make the string empty and we are having only 2 letters a and b. This made to a conclusion that we have 3 options:
1) Given string is empty, so return 0.
2) Given string is already palindrome, so remove the whole string which makes the step = 1. So just return 1.
**3) Given string is not palindrome, then consider removing 'a' or 'b' as the first step of remove. In this step we remove the complete 'a' and as a second step we remove the remaining letters 'a' or 'b'. So return 2 this time.
And this gives our whole problem.

ALGORITHM:

1) Check if given string empty, if true return 0.
2) Take 2 pointers left = 0, right = stringLength - 1
3) while left < right, do the following
-> check for palindromic condition, if fails return 2 else continue until the loops gets over.
4) return 1.

CODE

// here there are 3 conditions that we want to consider
// 1. if the string is empty, then return 0. This can be our first check.
// 2. Next one is checking palindrome or not. If the whole string is palindrome, then we can delete it completely. So return 1.
// 3. The next one is either we can remove a completely then b or vice versa. So in this case number of steps will be only 2. 
    // That is first step can be to remove all 'a's and the second step is remove all 'b's.
class Solution {
    public int removePalindromeSub(String s) {
        // string empty
        if (s.length() == 0)
            return 0;
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            // palindrome condition
            if (s.charAt(left) == s.charAt(right)) {
                left += 1;
                right -= 1;
            }
            else 
                return 2;
        }
        return 1;
    }
}

TIME COMPLEXITY: SPACE COMPLEXITY:
O(lengthOfString) O(1)

GITHUB LINK:Link