The answer to this question is way simpler than the question itself, it took much time to understand the question for me at least. But once you get the question, I am sure you'll get the answer by yourself.
Difficulty: Easy
Jump To:
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.
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'
Explanation
Did you get the question? If yes, then you are a PRO, if not then don't worry, you are normal, like me. So before understanding the question, let's first understand what are subsequence and palindrome.
-
Subsequence: 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. eg. for string
shivam
,ham
is a substring after deletings
,i
andv
. -
Substring: Don't confuse subsequence with substring. A substring is a contiguous sequence of characters within a string. eg. for string
shivam
,iva
is a substring whileham
is not. So it's clear that "All substrings are subsequences as well but not vice versa." -
Palindrome: A palindrome is a word, number, phrase, or other sequences of characters which reads the same backward as forward, such as
madam
orracecar
.
So the question wants to say that you can remove any subsequence from the string if it's a palindrome and the goal is to find that how many such deletion operations are needed to make the string empty.
Before going to the solution, do you want to see some hints? Here they are:
- Use the fact that the string contains only 2 characters.
- Are subsequences composed of only one type of letter always palindrome strings?
Solution
We are going to use the below ideas to solve this question:
- If any string is empty, then we don't need to do anything and return
0
. - If a string is a palindrome then we can delete the whole string in a single operation as a string is also a subsequence of itself. For such case, we need to return
1
. - A string of any length consists of a single type of character is always a subsequence eg.
aaaaa
,bbb
,a
etc. - So, I can delete a subsequence containing all characters of the same type from the string. eg. from string
aaabbbababa
I can removeaaaaaa
as it's a subsequence and palindrome as well. - And surprise, we are left with the string
bbbbb
which is also a palindrome so we can delete this in a single operation. - As the string can contain only
'a'
or'b'
only. So if the string is not palindrome then I can delete all the'a'
s in the first pass then all the'b'
s in the second pass, so the max operations we need is2
if the string is not a palindrome.
Implementation
C++ Code:
class Solution {
public:
int removePalindromeSub(string s) {
// Check if string is empty
if(s.empty())
return 0;
int len=s.size();
// Check for pallindrome
for(int i=0; i<=len/2; i++){
// If not pallindrome then 2 operations are needed
if(s[i] != s[len-i-1])
return 2;
}
// If pallindrome then only one operation is needed
return 1;
}
};
Runnable C++ Code:
Top comments (1)
It's working for me.
7/12 utara