1332. Remove Palindromic Subsequences LeetCode Solution

In this guide, you will get 1332. Remove Palindromic Subsequences LeetCode Solution with the best time and space complexity. The solution to Remove Palindromic Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Remove Palindromic Subsequences solution in C++
  4. Remove Palindromic Subsequences solution in Java
  5. Remove Palindromic Subsequences solution in Python
  6. Additional Resources
1332. Remove Palindromic Subsequences LeetCode Solution image

Problem Statement of Remove Palindromic Subsequences

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.

Example 1:

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

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

Constraints:

1 <= s.length <= 1000
s[i] is either 'a' or 'b'.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)
See also  1406. Stone Game III LeetCode Solution

1332. Remove Palindromic Subsequences LeetCode Solution in C++

class Solution {
 public:
  int removePalindromeSub(string s) {
    return equal(s.begin(), s.end(), s.rbegin()) ? 1 : 2;
  }
};
/* code provided by PROGIEZ */

1332. Remove Palindromic Subsequences LeetCode Solution in Java

class Solution {
  public int removePalindromeSub(String s) {
    return s.equals(new StringBuilder(s).reverse().toString()) ? 1 : 2;
  }
}
// code provided by PROGIEZ

1332. Remove Palindromic Subsequences LeetCode Solution in Python

class Solution:
  def removePalindromeSub(self, s: str) -> int:
    return 1 if s == s[::-1] else 2
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: