Skip to content

Latest commit

 

History

History

remove-palindromic-subsequences

README.md

Remove Palindromic Subsequences

Difficulty

Easy

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 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.

Example 1

Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

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".

Example 4

Input: s = ""
Output: 0

Constraints

0 <= s.length <= 1000

s only consists of letters 'a' and 'b'

Solutions (Click to expand)

Explanation

Maximum Two Moves

There are two observations to be made to reduce this into a maximum of two moves

Subsequences

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements. For palindromes this means that the characters of the palindrome don't necessarily have to be continuous. As long as we can derive a palindrome from the string without changing the order of the characters we can pick and choose which character we want to use to make a palindrome

"baabb" // we can group together all of the `b` characters without changing the order of the characters to make it into a palindrome
 ^  ^^

remove: bbb

"aa"
Single Letter Palindromes

Strings that contain only one type of character are palindromes, not matter the length.

// reversing these strings will result in the same string

"a" -> "a"

"aa" -> "aa"

"aaaaaaa" -> "aaaaaaa"
Conclusion

If we know that we can group all of the a and b characters of the string into to two subsequences both containing only one type of character, then we know that we can remove all of the characters with at max 2 palindromic subsequences. If the entire string itself is a palindrome then we can simply remove the entire string in one move since the entire string counts as palindromic subsequence If the string is empty there are no moves to be made

Implementation

  1. check to see if the string is empty. If it is there are 0 moves to be made

  2. check if the given string is a palindrome. This can be done several ways but preferably one that requires minimal space and operations (two pointer method works using O(1) space and O(n/2) operations). If it is a palindrome the entire string can be remove at once since it is a palindromic subsequence.

  3. Otherwise the string can be removed by group all the a characters and all the b characters into their own palindromic subsequences.

Time: O(N) Where N is the length of the string

Space: O(1)