Remove Palindromic Subsequences - Practice Coding Problems

Remove Palindromic Subsequences - 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 it reads the same backward as well as forward.

Input & Output

Example 1 — Not a Palindrome

$ Input: s = "abab"

› Output: 2

💡 Note: String "abab" is not a palindrome. We can remove all 'a's in step 1 ("aa" is palindrome) and all 'b's in step 2 ("bb" is palindrome).

Example 2 — Already Palindrome

$ Input: s = "aba"

› Output: 1

💡 Note: String "aba" is already a palindrome, so we can remove the entire string in 1 step.

Example 3 — Empty String

$ Input: s = ""

› Output: 0

💡 Note: Empty string requires 0 steps as there are no characters to remove.

Constraints

0 ≤ s.length ≤ 1000
s consists only of letters 'a' and 'b'

Visualization

Tap to expand

Understanding the Visualization

Input

String with only 'a' and 'b' characters

Analysis

Check if palindrome or needs 2 steps

Output

Minimum steps: 0, 1, or 2

Key Takeaway

🎯 Key Insight: With only 'a' and 'b' characters, any subsequence of identical characters forms a palindrome, so we need at most 2 steps

Asked in

F Facebook 15 G Google 8

The key insight is that with only characters 'a' and 'b', any subsequence of the same character forms a palindrome. Best approach uses mathematical reasoning: return 0 for empty string, 1 if string is already palindrome, otherwise 2. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Insight - Binary Alphabet	O(n)	O(1)	Realize that with only 'a' and 'b', the answer is always 0, 1, or 2
Brute Force - Check All Subsequences	O(2ⁿ)	O(2ⁿ)	Generate all possible subsequences and check which ones are palindromes
Two Pointers - Check Palindrome	O(n)	O(1)	Use two pointers to check if the entire string is already a palindrome

Mathematical Insight - Binary Alphabet — Algorithm Steps

Handle empty string case (return 0)
Check if entire string is palindrome (return 1)
Otherwise, always return 2 (remove all a's, then all b's)

Visualization

Tap to expand

Step-by-Step Walkthrough

Case Analysis

Empty→0, Palindrome→1, Other→2

Key Insight

All a's form palindrome, all b's form palindrome

Optimal

At most 2 steps needed for any input

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int isPalindrome(char* s) {
    int len = strlen(s);
    for (int i = 0; i < len/2; i++) {
        if (s[i] != s[len-1-i]) {
            return 0;
        }
    }
    return 1;
}

int solution(char* s) {
    // Empty string needs 0 steps
    if (strlen(s) == 0) {
        return 0;
    }
    
    // If entire string is palindrome, need only 1 step
    if (isPalindrome(s)) {
        return 1;
    }
    
    // Otherwise, always need exactly 2 steps:
    // Step 1: Remove all 'a's (palindrome)
    // Step 2: Remove all 'b's (palindrome)
    return 2;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to check if string is palindrome

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Insight - Binary Alphabet — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler