Given a string
s consisting only of letters
'b'. In a single step, you can remove one palindromic subsequence from
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.
Input: s = "ababa"
Explanation: String is already palindrome
Input: s = "abb"
Explanation: "abb" -> "bb" -> "".
Remove palindromic subsequence "a" then "bb".
Input: s = "baabb"
Explanation: "baabb" -> "b" -> "".
Remove palindromic subsequence "baab" then "b".
Input: s = ""
If we get an empty string, we can return 0 because there is nothing to delete.
If we have a palindrome, we can return 1 because a palindrome can be removed at once.
If not, we can return 2. (At first we can remove ‘a’ or ‘b’ and then we can remove the remaining string)
Time complexity:O(n), n is the length of the string
Space Complexity:O(1), no additional space is used
The code can be found in the following repository.
I have posted all the previous problems for the March LeetCoding Challenge 2021. You can check them out.
- March LeetCoding Challenge — Day 1 — Distribute Candies
- March LeetCoding Challenge — Day 2 — Set Mismatch
- March LeetCoding Challenge — Day 3 — Missing Number
- March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists
- March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree
- March LeetCoding Challenge — Day 6 — Short Encoding of Words