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
Top comments (0)