Remove Palindromic Subsequences - Leetcode Solution

Problem:

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 derived from the given string by deleting some or no characters without changing the order of the remaining characters.

A string is called palindrome if is one that reads the same backward as forward.

Example 1:

Input: s = "ababa" Output: 1 Explanation: String is already palindrome, we can remove one palindrome subsequence "ababa" which will make the string empty.

Example 2:

Input: s = "abb" Output: 2 Explanation: We can remove both "a" and "b" to make the string empty. Alternatively, we can remove "bb" and "a" one by one to make the string empty.

Example 3:

Input: s = "baabb" Output: 2 Explanation: "baabb" -> "b" -> "". Remove palindromic subsequence "baab" each time.

Solution:

The problem has a very small domain as we only have two letters 'a' and 'b'. We can use this to our advantage. A string is palindrome when it's relatively the same when reversed, we can say that it also has a standard structure as it's reading backward as it is forwards.

For example, "ababa" has a standard structure of "abcba" as when reversed, it reads the same as the original, and "babb" has a standard structure of "abba". The whole goal of this repetition scheme is to make sure that all the letters matching the starting letter are gathered and removed at once without worrying about the order of the letters.

So, we only need two steps to empty the string, first remove 'a' and then we can remove 'b' if it exists and the same for any other similar string. We can do so because the problem guaranteed have a string containing either one character or two, and both can be solved under the above condition.

So, if the string is non-empty, it has some palindromic structure which we can remove by following the above two steps, and in each step, one character is removed, and if the character is not there anymore, then it finishes the step without doing anything.

Therefore, the minimum number of steps to empty the given string is either 1 or 2 depending on whether it's a palindrome or not.

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the length of the given string.

Space Complexity:

The space complexity of the above algorithm is O(1) because we only use a constant amount of extra space to store some variables.

1