remove-palindromic-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a string <code>s</code> consisting only of letters <code>&#39;a&#39;</code> and <code>&#39;b&#39;</code>. In a single step you can remove one palindromic subsequence from <code>s</code>.

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 is one that reads the same backward as well as forward.

&nbsp;
Example 1:

<pre>
Input: s = &quot;ababa&quot;
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.
</pre>

Example 2:

<pre>
Input: s = &quot;abb&quot;
Output: 2
Explanation: &quot;abb&quot; -&gt; &quot;bb&quot; -&gt; &quot;&quot;. 
Remove palindromic subsequence &quot;a&quot; then &quot;bb&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;baabb&quot;
Output: 2
Explanation: &quot;baabb&quot; -&gt; &quot;b&quot; -&gt; &quot;&quot;. 
Remove palindromic subsequence &quot;baab&quot; then &quot;b&quot;.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s[i]</code> is either <code>&#39;a&#39;</code> or <code>&#39;b&#39;</code>.</li>
</ul>

removePalindromeSub

Remove Palindromic Subsequences

Two Pointers

String

给你一个字符串&nbsp;<code>s</code>，它仅由字母&nbsp;<code>'a'</code> 和 <code>'b'</code>&nbsp;组成。每一次删除操作都可以从 <code>s</code> 中删除一个回文 子序列。

返回删除给定字符串中所有字符（字符串为空）的最小删除次数。

「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。

「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

&nbsp;

示例 1：

<pre>
输入：s = "ababa"
输出：1
解释：字符串本身就是回文序列，只需要删除一次。
</pre>

示例 2：

<pre>
输入：s = "abb"
输出：2
解释："abb" -&gt; "bb" -&gt; "". 
先删除回文子序列 "a"，然后再删除 "bb"。
</pre>

示例 3：

<pre>
输入：s = "baabb"
输出：2
解释："baabb" -&gt; "b" -&gt; "". 
先删除回文子序列 "baab"，然后再删除 "b"。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> 仅包含字母&nbsp;<code>'a'</code>&nbsp; 和 <code>'b'</code></li>
</ul>