You are 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. Note that a subsequence does not necessarily need to be contiguous.
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: s is already a palindrome, so its entirety can be removed in a single step.
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".
Constraints:
1 <= s.length <= 1000s[i] is either 'a' or 'b'.If the input string is already a palindrome, then we can remove it in one step. If not, since the string contains only 'a' and 'b', we can always remove all 'a's in one step and all 'b's in another step, making at most two steps. Hence, the minimum number of steps to make the string empty is either 1 (if the string is a palindrome) or 2.
The function isPalindrome checks if the string is the same forwards and backwards. If it is a palindrome, the string can be removed in one step. Otherwise, since the string is composed of only 'a's and 'b's, we return 2 (removing all 'a's in one step and all 'b's in another step).
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of string s, as we need to potentially traverse the whole string to check if it's a palindrome.
Space Complexity: O(1), as we use only a few extra variables.
The second approach is based on the observation that the given string only consists of 'a' and 'b'. We can count the unique characters in the string. If the string is non-empty, it will always contain either 'a's or 'b's or both. If it contains both, removing all of one type and then the other would take two steps.
This C function checks if both 'a' and 'b' exist in the string using strchr. If both are found, it returns 2. Otherwise, if only one type exists, it only takes 1 step to remove.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Check If String is a Palindrome | Time Complexity: O(n), where n is the length of string s, as we need to potentially traverse the whole string to check if it's a palindrome. |
| Count Unique Characters and Remove | Time Complexity: O(n). |
Unique Length-3 Palindromic Subsequences - Leetcode 1930 - Python • NeetCode • 26,060 views views
Watch 9 more video solutions →Practice Remove Palindromic Subsequences with our built-in code editor and test cases.
Practice on FleetCode