DEV Community

Cover image for March LeetCoding Challenge 2021 — Day 8: Remove Palindromic Subsequences
Sourav
Sourav

Posted on

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
Enter fullscreen mode Exit fullscreen mode

Example 2:

**Input:** s = "abb"
**Output:** 2
**Explanation:** "**a**bb" -> "**bb**" -> "". 
Remove palindromic subsequence "a" then "bb".
Enter fullscreen mode Exit fullscreen mode

Example 3:

**Input:** s = "baabb"
**Output:** 2
**Explanation:** "**baa**b**b**" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".
Enter fullscreen mode Exit fullscreen mode

Example 4:

**Input:** s = ""
**Output:** 0
Enter fullscreen mode Exit fullscreen mode

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.

LeetCode

I have been solving Leetcode problems for around a year or so. Suddenly I have developed a passion of writing tutorials for these problems. I am starting with Leetcode problem, in future I will try to make tutorials on Spring,Android,Java,Algorithms and many more.

Follow me on medium - https://sourav-saikia.medium.com
Follow me on dev.to - https://dev.to/sksaikia
Follow me on twitter - https://twitter.com/sourav__saikia
Connect on Linkedin - www.linkedin.com/in/sourav-kumar-saikia

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

March LeetCoding Challenge

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

  1. March LeetCoding Challenge — Day 1 — Distribute Candies

  2. March LeetCoding Challenge — Day 2 — Set Mismatch

  3. March LeetCoding Challenge — Day 3 — Missing Number

  4. March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists

  5. March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree

  6. March LeetCoding Challenge — Day 6 — Short Encoding of Words

Top comments (0)