can-make-palindrome-from-substring

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> and array <code>queries</code> where <code>queries[i] = [lefti, righti, ki]</code>. We may rearrange the substring <code>s[lefti...righti]</code> for each query and then choose up to <code>ki</code> of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is <code>true</code>. Otherwise, the result is <code>false</code>.

Return a boolean array <code>answer</code> where <code>answer[i]</code> is the result of the <code>ith</code> query <code>queries[i]</code>.

Note that each letter is counted individually for replacement, so if, for example <code>s[lefti...righti] = &quot;aaa&quot;</code>, and <code>ki = 2</code>, we can only replace two of the letters. Also, note that no query modifies the initial string <code>s</code>.

&nbsp;
Example :

<pre>
Input: s = &quot;abcda&quot;, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0]: substring = &quot;d&quot;, is palidrome.
queries[1]: substring = &quot;bc&quot;, is not palidrome.
queries[2]: substring = &quot;abcd&quot;, is not palidrome after replacing only 1 character.
queries[3]: substring = &quot;abcd&quot;, could be changed to &quot;abba&quot; which is palidrome. Also this can be changed to &quot;baab&quot; first rearrange it &quot;bacd&quot; then replace &quot;cd&quot; with &quot;ab&quot;.
queries[4]: substring = &quot;abcda&quot;, could be changed to &quot;abcba&quot; which is palidrome.
</pre>

Example 2:

<pre>
Input: s = &quot;lyb&quot;, queries = [[0,1,0],[2,2,1]]
Output: [false,true]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length, queries.length &lt;= 105</code></li>
	<li><code>0 &lt;= lefti &lt;= righti &lt; s.length</code></li>
	<li><code>0 &lt;= ki &lt;= s.length</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

canMakePaliQueries

Can Make Palindrome from Substring

Plates Between Candles

plates-between-candles

蜡烛之间的盘子

Maximize the Number of Partitions After Operations

maximize-the-number-of-partitions-after-operations

执行操作后的最大分割数量

Bit Manipulation

Array

Hash Table

String

Prefix Sum

给你一个字符串&nbsp;<code>s</code>，请你对&nbsp;<code>s</code>&nbsp;的子串进行检测。

每次检测，待检子串都可以表示为&nbsp;<code>queries[i] = [left, right, k]</code>。我们可以 重新排列 子串&nbsp;<code>s[left], ..., s[right]</code>，并从中选择 最多 <code>k</code>&nbsp;项替换成任何小写英文字母。&nbsp;

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为&nbsp;<code>true</code>，否则结果为&nbsp;<code>false</code>。

返回答案数组&nbsp;<code>answer[]</code>，其中&nbsp;<code>answer[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个待检子串&nbsp;<code>queries[i]</code>&nbsp;的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果&nbsp;<code>s[left..right] = &quot;aaa&quot;</code>&nbsp;且&nbsp;<code>k = 2</code>，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 <code>s</code>，可以认为每次检测都是独立的）

&nbsp;

示例：

<pre>输入：s = &quot;abcda&quot;, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = &quot;d&quot;，回文。
queries[1] :&nbsp;子串 = &quot;bc&quot;，不是回文。
queries[2] :&nbsp;子串 = &quot;abcd&quot;，只替换 1 个字符是变不成回文串的。
queries[3] :&nbsp;子串 = &quot;abcd&quot;，可以变成回文的 &quot;abba&quot;。 也可以变成 &quot;baab&quot;，先重新排序变成 &quot;bacd&quot;，然后把 &quot;cd&quot; 替换为 &quot;ab&quot;。
queries[4] :&nbsp;子串 = &quot;abcda&quot;，可以变成回文的 &quot;abcba&quot;。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length,&nbsp;queries.length&nbsp;&lt;= 10^5</code></li>
	<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt;&nbsp;s.length</code></li>
	<li><code>0 &lt;= queries[i][2] &lt;= s.length</code></li>
	<li><code>s</code> 中只有小写英文字母</li>
</ul>