Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Remove Palindromic Subsequences solution and explanation

EasyStringTwo Pointers5 min read77.1% acceptanceUpdated 9 Apr 2026
Asked atAmazon
Practise Remove Palindromic Subsequences
4:25
Leetcode 1332. Remove Palindromic SubsequencesFraz · 4:25 · 12K viewsWatch on YouTube
9 more videos on this problem
  1. Leetcode 1332. Remove Palindromic SubsequencesFraz · 4:25 · 12K views
  2. Remove Palindromic Subsequences | Live Coding with Explanation | Leetcode - 1332Algorithms Made Easy · 5:01 · 5K views
  3. Remove Palindromic Subsequences | Leetcode 1332 | StringsAyushi Sharma · 9:19 · 3K views
  4. Leetcode 1332. Remove Palindromic SubsequencesCode with Alisha · 6:16 · 2K views
  5. Leetcode - Remove Palindromic Subsequences (Python)Timothy H Chang · 3:52 · 1K views
  6. Remove Palindromic Subsequences | Leetcode 1332Coding Decoded · 8:09 · 868 views
  7. Daily Leetcode #799: Jun 08, 2022 - 1332. Remove Palindromic SubsequencesProgramming Live with Larry · 5:19 · 421 views
  8. 2 pointers | 1332 Remove Palindromic Subsequences - LeetCodeCoding BeTounsi · 5:16 · 308 views
  9. 1332. Remove Palindromic Subsequences | LEETCODE EASY | GREEDY | CODE EXPLAINERcode Explainer · 5:57 · 296 views
  10. Daily Leetcode #342: Mar 08, 2021 - 1332. Remove Palindromic SubsequencesProgramming Live with Larry · 7:59 · 262 views

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

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

Approach overview

Problem Overview: You are given a string s containing only the characters 'a' and 'b'. In one operation, you can remove any subsequence that forms a palindrome. The task is to return the minimum number of operations required to delete the entire string.

Approach 1: Check If String is a Palindrome (O(n) time, O(1) space)

The key observation: because the string contains only two characters (a and b), the answer can never exceed 2. If the entire string is already a palindrome, you can remove it in one operation. Otherwise, remove all a characters in one step and all b characters in another. To verify the first case, use the two pointers technique—place one pointer at the start and one at the end, then move inward while comparing characters. If every pair matches, the string is a palindrome and the answer is 1. If any mismatch appears, the answer must be 2.

This works because any sequence of identical characters is itself a palindrome. Even if the full string is not symmetric, removing all as forms one palindromic subsequence and removing all bs forms another. The check itself is linear since each character is visited once.

Approach 2: Count Unique Characters and Remove (O(n) time, O(1) space)

Another way to reason about the problem is by counting distinct characters in the string. Since subsequences do not need to be contiguous, all occurrences of the same character can be removed together as a palindrome (for example, "aaaa"). Scan the string and track the set of unique characters using simple frequency checks. If only one character appears, the whole string is already a palindrome and can be removed in one operation.

If two characters exist (a and b), you can always remove them in exactly two steps: remove the subsequence containing all as, then remove all bs. This approach treats the problem as a property of the string composition rather than checking symmetry. The scan is linear and uses constant extra memory.

Recommended for interviews: The palindrome check using two pointers is usually expected. It shows you recognize the constraint that the answer is at most two and can verify the palindrome condition efficiently. The character-count reasoning is equally valid but the two-pointer explanation demonstrates stronger familiarity with common two pointer patterns used in string problems.

Approach 1: Check If String is a Palindrome

If the input string is already a palindrome, then we can remove it in one step. If not, since the string contains only 'a' and 'b', we can always remove all 'a's in one step and all 'b's in another step, making at most two steps. Hence, the minimum number of steps to make the string empty is either 1 (if the string is a palindrome) or 2.

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        return 1 if s == s[::-1] else 2
class Solution {
    public int removePalindromeSub(String s) {
        return isPalindrome(s) ? 1 : 2;
    }
    
    private boolean isPalindrome(String s) {
        int start = 0, end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}
#include <string>

class Solution {
public:
    int removePalindromeSub(std::string s) {
        return std::string(s.rbegin(), s.rend()) == s ? 1 : 2;
    }
};
function removePalindromeSub(s) {
    const isPalindrome = (s) => {
        let l = 0, r = s.length - 1;
        while (l < r) {
            if (s[l++] !== s[r--]) return false;
        }
        return true;
    };
    return isPalindrome(s) ? 1 : 2;
}
#include <string.h>
#include <stdbool.h>

bool isPalindrome(const char *s) {
    int start = 0, end = strlen(s) - 1;
    while (start < end) {
        if (s[start++] != s[end--]) {
            return false;
        }
    }
    return true;
}

int removePalindromeSub(char *s) {
    return isPalindrome(s) ? 1 : 2;
}
public class Solution {
    public int RemovePalindromeSub(string s) {
        return IsPalindrome(s) ? 1 : 2;
    }
    
    private bool IsPalindrome(string s) {
        int start = 0, end = s.Length - 1;
        while (start < end) {
            if (s[start++] != s[end--]) {
                return false;
            }
        }
        return true;
    }
}

The Python solution checks if the string s is a palindrome by comparing it to its reverse s[::-1]. If they are equal, return 1; otherwise, return 2.

Complexity

Time Complexity: O(n).
Space Complexity: O(n).

Try this approach in the editor

Approach 2: Count Unique Characters and Remove

The second approach is based on the observation that the given string only consists of 'a' and 'b'. We can count the unique characters in the string. If the string is non-empty, it will always contain either 'a's or 'b's or both. If it contains both, removing all of one type and then the other would take two steps.

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        return 1 if 'a' not in s or 'b' not in s else 2
class Solution {
    public int removePalindromeSub(String s) {
        if (s.isEmpty()) return 0;
        boolean hasA = s.indexOf('a') != -1;
        boolean hasB = s.indexOf('b') != -1;
        return hasA && hasB ? 2 : 1;
    }
}
#include <string>

class Solution {
public:
    int removePalindromeSub(std::string s) {
        return s.empty() ? 0 : (s.find('a') != std::string::npos && s.find('b') != std::string::npos ? 2 : 1);
    }
};
function removePalindromeSub(s) {
    if (!s) return 0;
    if (s.includes('a') && s.includes('b')) return 2;
    return 1;
}
#include <string.h>

int removePalindromeSub(char *s) {
    if (!*s) return 0;
    int ab = strchr(s, 'a') && strchr(s, 'b');
    return ab ? 2 : 1;
}
public class Solution {
    public int RemovePalindromeSub(string s) {
        if (string.IsNullOrEmpty(s)) return 0;
        bool hasA = s.Contains('a');
        bool hasB = s.Contains('b');
        return hasA && hasB ? 2 : 1;
    }
}

Checks for the presence of both 'a' and 'b' in the string and returns the step count accordingly. If only one character type is present, it returns 1; otherwise, it returns 2.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Default Approach

function removePalindromeSub(s: string): number {
    for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
        if (s[i] !== s[j]) {
            return 2;
        }
    }
    return 1;
}
func removePalindromeSub(s string) int {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return 2
		}
	}
	return 1
}
impl Solution {
    pub fn remove_palindrome_sub(s: String) -> i32 {
        let mut l = 0;
        let mut r = s.len() - 1;
        let s: Vec<char> = s.chars().collect();
        while l < r {
            if s[l] != s[r] {
                return 2;
            }
            l += 1;
            r -= 1;
        }
        1
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Check If String is a Palindrome

Time Complexity: O(n).
Space Complexity: O(n).

Count Unique Characters and Remove

Time Complexity: O(n).
Space Complexity: O(1).

Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Check if Entire String is Palindrome (Two Pointers)O(n)O(1)Best general solution. Quickly determines if the whole string can be removed in one step.
Count Unique CharactersO(n)O(1)Useful when reasoning about character composition rather than symmetry.

Frequently asked questions

Is Remove Palindromic Subsequences easy or hard?

Remove Palindromic Subsequences is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge lies in recognizing the key observation that only two operations are ever needed due to the limited character set.

Remove Palindromic Subsequences Python/Java solution

Most implementations check whether the string equals its reverse (Python) or use two pointers moving inward (Java/C++). If the string is empty return 0, if it is a palindrome return 1, otherwise return 2. The logic is simple and runs in linear time.

How to solve Remove Palindromic Subsequences in O(n)?

Traverse the string using two pointers from both ends. If all mirrored characters match, the string is a palindrome and the answer is 1. If a mismatch appears, the answer becomes 2 because you can remove all 'a' characters in one operation and all 'b' characters in another. The scan touches each character once, giving O(n) time complexity.

What is the best approach for Remove Palindromic Subsequences?

The optimal approach checks whether the entire string is already a palindrome using the two pointers technique. If the string is a palindrome, it can be removed in one operation. Otherwise, remove all 'a' characters in one step and all 'b' characters in another, resulting in at most two operations. This solution runs in O(n) time and O(1) space.

Is Remove Palindromic Subsequences asked at Google/Amazon/Meta?

Palindrome and string manipulation problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, its core ideas—two pointers and palindrome checks—are common interview patterns.

What data structure is used in Remove Palindromic Subsequences?

The main technique relies on two pointers for palindrome verification. Some explanations also use a small set or frequency counter to track unique characters in the string. Both approaches operate with constant extra memory.

What is the time complexity of Remove Palindromic Subsequences?

The optimal solution runs in O(n) time where n is the length of the string. You perform a single pass to check whether the string is a palindrome or to inspect the characters present. Space complexity remains O(1) because only a few pointers or counters are required.

Comments

Now write it yourselfClose this page and solve Remove Palindromic Subsequences in the editor, without looking.
Practise Remove Palindromic Subsequences