# March LeetCoding Challenge 2021 — Day 8: Remove Palindromic Subsequences

Today, we will solve the 8th problem of the March LeetCoding Challenge.

# Problem Statement

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:** "**a**bb" -> "**bb**" -> "".

Remove palindromic subsequence "a" then "bb".

**Example 3:**

**Input:** s = "baabb"

**Output:** 2

**Explanation:** "**baa**b**b**" -> "b" -> "".

Remove palindromic subsequence "baab" then "b".

**Example 4:**

**Input:** s = ""

**Output:** 0

# Solution

If we get an empty string, we can return 0 because there is nothing to delete.

If we have a palindrome, we can return 1 because a palindrome can be removed at once.

If not, we can return 2. (At first we can remove ‘a’ or ‘b’ and then we can remove the remaining string)

Time complexity:O(n), n is the length of the string

Space Complexity:O(1), no additional space is used

The code can be found in the following repository.

I have posted all the previous problems for the March LeetCoding Challenge 2021. You can check them out.

- March LeetCoding Challenge — Day 1 — Distribute Candies
- March LeetCoding Challenge — Day 2 — Set Mismatch
- March LeetCoding Challenge — Day 3 — Missing Number
- March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists
- March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree
- March LeetCoding Challenge — Day 6 — Short Encoding of Words