1332. Remove Palindromic Subsequences (Easy)

寫在前面

Question

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.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1

1
2
3

Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Example 2

1
2
3
4

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "".
Remove palindromic subsequence "a" then "bb".

Example 3

1
2
3
4

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "".
Remove palindromic subsequence "baab" then "b".

Example 4

1
2

Input: s = ""
Output: 0

Constraints

• 0 <= s.length <= 1000
• s only consists of letters ‘a’ and ‘b’

分析/解題

給定一個字串，當中僅由’a’或’b’的字母所構成，每次你可以從中移除一個palindrome subsequence. 試回傳將該字串刪成空字串所需的最小步數。

我們先前有講過subsequence的定義，可以參照之前的題目 。
所以每次要移除掉一個subsequence且必須符合palindrome的條件，
乍看之下似乎不容易。
但選這題的目的就是要告訴大家，有時候事情並沒有想像中那麼複雜，
靜下心來好好推敲，可能可以找到適合的規律，
不要急著找通解，先試著去用上所有已知的條件 看看才對！

我們知道subsequence就是按照排列的先後順序取就可以了，
但palindrome(回文) 則必須取出來從頭到尾和從尾到頭一致才行。

我們先考慮最簡單的部分，再慢慢往下推。
1. 當字串是空白的時候：
不需操作 即可達到條件，所以總step為0。
2. 當字串本身就是palindrome：
把整個字串做為subsequence移除，所以總step為1。

接下來是最重要的部分，
如果字串本身不是palindrome的話，
要怎麼樣才會移除一個palindrome sequence後，
可以用最小步數化簡呢？
由於s僅僅由’a’和’b’所組成 ，
所以我們可以考慮直接移去全部的’a’或全部的’b’，
由於全部都是’a’或全部都是’b’也是一種palindrome，
所以符合前面移除的規則；
而剩下來的就全部都是另外一種字元，
同樣也構成palindrome。
因此，最多只要2個step，就能全數移完。

(想一下，如果今天是有N種不同的字元構成s，
最多就會需要N個step，但這只是上限而已，而不是minimum steps。)

有興趣寫更細的話，可以用two pointer來寫這題的檢查palindrome的部分，
這裡就直接用簡單的操作處理。

Java

Java的部分，操作reverse 要使用StringBuilder 來處理，
處理完以後，再轉回String。

Python

Python的部分更精簡，使用**[::-1]** 即可表達從尾到頭 的部分。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，若願意一個一個字元比較的話，
空間複雜度也可以降到O(1)，也就是用簡單的two pointer處理即可)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**