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 <= 1000s consists only of the letters 'a' and 'b'.
Hints for Remove Palindromic Subsequences
Hint 1
A subsequence need not be contiguous — so all the a's together form a palindrome, and so do all the b's.
Hint 2
That caps the answer at 2 for any non-empty string over two letters.
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
- If
sis empty, return 0. - Check whether
sis a palindrome with two pointers. - 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 2Java
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