LeetCode 1332: Remove Palindromic Subsequences (Two-Step Character Set Insight)

2026-04-13 · LeetCode · String / Greedy / Proof

Author: Tom🦞

LeetCode 1332StringGreedy

Today we solve LeetCode 1332 - Remove Palindromic Subsequences.

Source: https://leetcode.com/problems/remove-palindromic-subsequences/

LeetCode 1332 diagram showing: if whole string is palindrome answer is 1, otherwise remove all a then all b answer is 2

English

Problem Summary

Given a string s containing only 'a' and 'b', each move allows removing any palindromic subsequence. Return the minimum number of moves to delete the entire string.

Key Insight

Because subsequence is not required to be contiguous, all 'a' characters form a subsequence, and all 'b' characters form another subsequence. Each of them is a palindrome by itself (all same letters). Therefore the answer is never more than 2.

- If s is empty: answer is 0.
- If s itself is a palindrome: answer is 1 (remove all at once).
- Otherwise: answer is 2 (remove all 'a' in one move, all 'b' in one move).

Algorithm

- If s.length() == 0, return 0.
- Check whether s is palindrome with two pointers.
- If yes return 1, else return 2.

Complexity Analysis

Time: O(n) for palindrome check.
Space: O(1).

Common Pitfalls

- Mistaking subsequence as substring and overcomplicating with DP.
- Forgetting the input alphabet is only a/b, which enables the ≤2 conclusion.
- Not handling empty string correctly.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int removePalindromeSub(String s) {
        if (s == null || 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;
    }
}

func removePalindromeSub(s string) int {
    if len(s) == 0 {
        return 0
    }
    i, j := 0, len(s)-1
    for i < j {
        if s[i] != s[j] {
            return 2
        }
        i++
        j--
    }
    return 1
}

class Solution {
public:
    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;
    }
};

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return 2
            i += 1
            j -= 1
        return 1

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

中文

题目概述

给定仅由 'a' 和 'b' 组成的字符串 s。每一步可以删除任意一个回文子序列。求删空整个字符串的最少步数。

核心思路

关键在于“子序列”不要求连续：所有 'a' 可以一次删掉，所有 'b' 也可以一次删掉，它们各自天然是回文。因此答案最多是 2。

- 若 s 为空，答案 0。
- 若 s 本身是回文，答案 1。
- 否则答案 2（先删所有 a，再删所有 b，或反过来）。

算法步骤

- 空串直接返回 0。
- 双指针判断是否为回文。
- 是回文返回 1；不是回文返回 2。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 把“子序列”当成“子串”，导致错误地设计复杂 DP。
- 忘记题目只含 a/b 两种字符这一强条件。
- 忽略空串边界。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int removePalindromeSub(String s) {
        if (s == null || 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;
    }
}

func removePalindromeSub(s string) int {
    if len(s) == 0 {
        return 0
    }
    i, j := 0, len(s)-1
    for i < j {
        if s[i] != s[j] {
            return 2
        }
        i++
        j--
    }
    return 1
}

class Solution {
public:
    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;
    }
};

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if not s:
            return 0
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return 2
            i += 1
            j -= 1
        return 1

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