Sponsored
Sponsored
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.
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.
1class Solution {
2 public int removePalindromeSub(String s) {
3 return isPalindrome(s) ? 1 : 2;
4 }
5
6 private boolean isPalindrome(String s) {
7 int start = 0, end = s.length() - 1;
8 while (start < end) {
9 if (s.charAt(start++) != s.charAt(end--)) {
10 return false;
11 }
12 }
13 return true;
14 }
15}This Java function uses a helper method to check if the string is a palindrome. If it is, we remove it in one step, otherwise in two steps.
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.
Time Complexity: O(n).
Space Complexity: O(1).
1
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.