Remove Palindromic Subsequences

Easy
526.

Remove Palindromic Subsequences

Remove Palindromic Subsequences is an easy coding problem on strings and two pointers, asked in Amazon and Google interviews.

You are given a string s made only of the letters 'a' and 'b'.

In one step you may delete any palindromic subsequence from s — the remaining characters close up. Return the minimum number of steps needed to make s empty.

Example 1

Input
s = "ababa"
Output
1
Explanation
The whole string is already a palindrome.

Example 2

Input
s = "abb"
Output
2
Explanation
Delete the subsequence "bb", then delete "a".

Example 3

Input
s = "baabb"
Output
2

Constraints

  • 1 <= s.length <= 1000
  • s consists only of the letters 'a' and 'b'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var removePalindromeSub = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Palindromic Subsequences — Problem & Solution

Remove Palindromic Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Remove Palindromic Subsequences is an easy coding problem on strings and two pointers, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Strings, Two Pointers
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s made only of the letters 'a' and 'b'.

In one step you may delete any palindromic subsequence from s — the remaining characters close up. Return the minimum number of steps needed to make s empty.

Example 1

Input: s = "ababa"
Output: 1
Explanation: The whole string is already a palindrome.

Example 2

Input: s = "abb"
Output: 2
Explanation: Delete the subsequence "bb", then delete "a".

Example 3

Input: s = "baabb"
Output: 2

Constraints

  • 1 <= s.length <= 1000
  • s consists only of the letters 'a' and 'b'.

Hints for Remove Palindromic Subsequences

  1. Hint 1

    A subsequence need not be contiguous — so all the a's together form a palindrome, and so do all the b's.

  2. Hint 2

    That caps the answer at 2 for any non-empty string over two letters.

  3. Hint 3

    The only question left is whether one step suffices.

How to solve Remove Palindromic Subsequences

With only two distinct letters the answer is always 0, 1 or 2: delete all a's then all b's. So the whole problem reduces to a palindrome check.

Approach

  1. If s is empty, return 0.
  2. Check whether s is a palindrome with two pointers.
  3. Return 1 if it is, otherwise 2.

Why it works

All occurrences of a single letter form a palindromic subsequence, so two steps always suffice. One step is possible exactly when s itself is a palindrome, and zero only when it is already empty.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Reading "subsequence" as "substring" makes the problem look much harder and gives wrong answers.
  • Forgetting the empty-string case returns 1 instead of 0 — though the stated constraints exclude it.
  • Trying dynamic programming here is a large detour for a two-line answer.

Reference solution

Python

def removePalindromeSub(s: str) -> int:
    if not s:
        return 0
    return 1 if s == s[::-1] else 2

Java

public static int removePalindromeSub(String s) {
    if (s.length() == 0) return 0;
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return 2;
        i++;
        j--;
    }
    return 1;
}

C++

int removePalindromeSub(string s) {
    if (s.empty()) return 0;
    int i = 0, j = (int) s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return 2;
        i++;
        j--;
    }
    return 1;
}

JavaScript

var removePalindromeSub = function(s) {
    if (s.length === 0) return 0;
    let i = 0, j = s.length - 1;
    while (i < j) {
        if (s.charAt(i) !== s.charAt(j)) return 2;
        i++;
        j--;
    }
    return 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Two Pointers Technique