Remove Palindromic Subsequences Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5

Input:
s = "ababa"
Output:
 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

1
2
3
4
5
6

Input:
s = "abb"
Output:
 2
Explanation: "abb" -> "bb" -> "".
Remove palindromic subsequence "a" then "bb".

Example 3:

1
2
3
4
5
6

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

Solution

Method 1 – At Most 2 Operations

Intuition

The problem becomes simple due to the restriction that the string s contains only the characters 'a' and 'b'. Any subsequence made up of only one character is always a palindrome. This means we can always remove all 'a's or all 'b's in a single operation. If the entire string is already a palindrome, we can remove it in one go. Otherwise, we can remove all of one character type in one step and the rest in the next, guaranteeing the string is emptied in at most two steps.

Approach

1. Check for Palindrome:

   • If s is a palindrome, remove the whole string in one operation and return 1.

2. Remove by Character Type:

   • If s is not a palindrome, remove all 'a's in one operation (as a palindromic subsequence), then remove all 'b's in the next operation. This works because any sequence of identical characters is a palindrome, and after removing all of one type, the remainder is also a palindrome.

3. Edge Case:

   • If s is empty, return 0 since no operations are needed.

Additional Clarifications

• Why check if the string is a palindrome?

  • If s is a palindrome, we can remove it in one go, which is optimal.

• Why does the solution work for only two characters?

  • With only 'a' and 'b', after removing all of one character, the remaining string is made up of the other character, which is itself a palindrome.

• What if the string contains more than two characters?

  • The logic would not hold; this approach is specific to the constraint that s contains only 'a' and 'b'.

• Why not use a more complex algorithm?

  • The constraints and properties of the problem allow for this direct and optimal solution.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
	int removePalindromeSub(string s) {
		if (s.empty()) return 0;
		int i = 0, j = s.size() - 1;
		while (i < j) {
			if (s[i++] != s[j--]) return 2;
		}
		return 1;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func removePalindromeSub(s string) int {
	if len(s) == 0 {
		return 0
	}
	i, j := 0, len(s)-1
	for i < j {
		if s[i] != s[j] {
			return 2
		}
		i++
		j--
	}
	return 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	public int removePalindromeSub(String s) {
		if (s.length() == 0) return 0;
		int i = 0, j = s.length() - 1;
		while (i < j) {
			if (s.charAt(i++) != s.charAt(j--)) return 2;
		}
		return 1;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun removePalindromeSub(s: String): Int {
		if (s.isEmpty()) return 0
		var i = 0
		var j = s.length - 1
		while (i < j) {
			if (s[i] != s[j]) return 2
			i++
			j--
		}
		return 1
	}
}

1
2
3
4
5
6
7

class Solution:
	def removePalindromeSub(self, s: str) -> int:
		if not s:
			return 0
		if s == s[::-1]:
			return 1
		return 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
	pub fn remove_palindrome_sub(s: String) -> i32 {
		if s.is_empty() {
			return 0;
		}
		let bytes = s.as_bytes();
		let (mut i, mut j) = (0, bytes.len() - 1);
		while i < j {
			if bytes[i] != bytes[j] {
				return 2;
			}
			i += 1;
			j -= 1;
		}
		1
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function removePalindromeSub(s: string): number {
	if (s.length === 0) return 0;
	let i = 0, j = s.length - 1;
	while (i < j) {
		if (s[i] !== s[j]) return 2;
		i++;
		j--;
	}
	return 1;
}

Complexity

• ⏰ Time complexity: O(N) where N is the length of s, since we may need to check every character to determine if s is a palindrome.
• 🧺 Space complexity: O(1) extra space, as we only use a few variables for pointers and counters.