maximum-number-of-removable-characters

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 two strings <code>s</code> and <code>p</code> where <code>p</code> is a subsequence of <code>s</code>. You are also given a distinct 0-indexed integer array <code>removable</code> containing a subset of indices of <code>s</code> (<code>s</code> is also 0-indexed).

You want to choose an integer <code>k</code> (<code>0 &lt;= k &lt;= removable.length</code>) such that, after removing <code>k</code> characters from <code>s</code> using the first <code>k</code> indices in <code>removable</code>, <code>p</code> is still a subsequence of <code>s</code>. More formally, you will mark the character at <code>s[removable[i]]</code> for each <code>0 &lt;= i &lt; k</code>, then remove all marked characters and check if <code>p</code> is still a subsequence.

Return the maximum <code>k</code> you can choose such that <code>p</code> is still a subsequence of <code>s</code> after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

&nbsp;
Example 1:

<pre>
Input: s = &quot;abcacb&quot;, p = &quot;ab&quot;, removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, &quot;a<s>b</s>c<s>a</s>cb&quot; becomes &quot;accb&quot;.
&quot;ab&quot; is a subsequence of &quot;accb&quot;.
If we remove the characters at indices 3, 1, and 0, &quot;<s>ab</s>c<s>a</s>cb&quot; becomes &quot;ccb&quot;, and &quot;ab&quot; is no longer a subsequence.
Hence, the maximum k is 2.
</pre>

Example 2:

<pre>
Input: s = &quot;abcbddddd&quot;, p = &quot;abcd&quot;, removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, &quot;abc<s>b</s>ddddd&quot; becomes &quot;abcddddd&quot;.
&quot;abcd&quot; is a subsequence of &quot;abcddddd&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;abcab&quot;, p = &quot;abc&quot;, removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, &quot;abc&quot; is no longer a subsequence.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= p.length &lt;= s.length &lt;= 105</code></li>
	<li><code>0 &lt;= removable.length &lt; s.length</code></li>
	<li><code>0 &lt;= removable[i] &lt; s.length</code></li>
	<li><code>p</code> is a subsequence of <code>s</code>.</li>
	<li><code>s</code> and <code>p</code> both consist of lowercase English letters.</li>
	<li>The elements in <code>removable</code> are distinct.</li>
</ul>

maximumRemovals

Maximum Number of Removable Characters

Maximum Candies Allocated to K Children

maximum-candies-allocated-to-k-children

每个小孩最多能分到多少糖果

Array

Two Pointers

String

Binary Search

给你两个字符串 <code>s</code> 和 <code>p</code> ，其中 <code>p</code> 是 <code>s</code> 的一个 子序列 。同时，给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组 <code>removable</code> ，该数组是 <code>s</code> 中下标的一个子集（<code>s</code> 的下标也 从 0 开始 计数）。

请你找出一个整数 <code>k</code>（<code>0 <= k <= removable.length</code>），选出 <code>removable</code> 中的 前 <code>k</code> 个下标，然后从 <code>s</code> 中移除这些下标对应的 <code>k</code> 个字符。整数 <code>k</code> 需满足：在执行完上述步骤后， <code>p</code> 仍然是 <code>s</code> 的一个 子序列 。更正式的解释是，对于每个 <code>0 <= i < k</code> ，先标记出位于 <code>s[removable[i]]</code> 的字符，接着移除所有标记过的字符，然后检查 <code>p</code> 是否仍然是 <code>s</code> 的一个子序列。

返回你可以找出的 最大 <code>k</code> ，满足在移除字符后 <code>p</code> 仍然是 <code>s</code> 的一个子序列。

字符串的一个 子序列 是一个由原字符串生成的新字符串，生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。

 

示例 1：

<pre>
输入：s = "abcacb", p = "ab", removable = [3,1,0]
输出：2
解释：在移除下标 3 和 1 对应的字符后，"abcacb" 变成 "accb" 。
"ab" 是 "accb" 的一个子序列。
如果移除下标 3、1 和 0 对应的字符后，"abcacb" 变成 "ccb" ，那么 "ab" 就不再是 s 的一个子序列。
因此，最大的 k 是 2 。
</pre>

示例 2：

<pre>
输入：s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
输出：1
解释：在移除下标 3 对应的字符后，"abcbddddd" 变成 "abcddddd" 。
"abcd" 是 "abcddddd" 的一个子序列。
</pre>

示例 3：

<pre>
输入：s = "abcab", p = "abc", removable = [0,1,2,3,4]
输出：0
解释：如果移除数组 removable 的第一个下标，"abc" 就不再是 s 的一个子序列。
</pre>

 

提示：

<ul>
	<li><code>1 <= p.length <= s.length <= 105</code></li>
	<li><code>0 <= removable.length < s.length</code></li>
	<li><code>0 <= removable[i] < s.length</code></li>
	<li><code>p</code> 是 <code>s</code> 的一个 子字符串</li>
	<li><code>s</code> 和 <code>p</code> 都由小写英文字母组成</li>
	<li><code>removable</code> 中的元素 互不相同</li>
</ul>