mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-12 10:51:42 +08:00
73 lines
3.3 KiB
HTML
73 lines
3.3 KiB
HTML
<p>给你一个下标从 <strong>0</strong> 开始的字符串 <code>s</code> 和一个整数 <code>k</code>。</p>
|
||
|
||
<p>你需要执行以下分割操作，直到字符串 <code>s </code>变为 <strong>空</strong>：</p>
|
||
|
||
<ul>
|
||
<li>选择 <code>s</code> 的最长 <strong>前缀</strong>，该前缀最多包含 <code>k </code>个 <strong>不同 </strong>字符。</li>
|
||
<li><strong>删除 </strong>这个前缀，并将分割数量加一。如果有剩余字符，它们在 <code>s</code> 中保持原来的顺序。</li>
|
||
</ul>
|
||
|
||
<p>执行操作之 <strong>前</strong> ，你可以将 <code>s</code> 中 <strong>至多一处 </strong>下标的对应字符更改为另一个小写英文字母。</p>
|
||
|
||
<p>在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的 <strong>最大</strong> 分割数量。</p>
|
||
|
||
<p> </p>
|
||
|
||
<p><strong class="example">示例 1：</strong></p>
|
||
|
||
<div class="example-block">
|
||
<p><strong>输入：</strong><span class="example-io">s = "accca", k = 2</span></p>
|
||
|
||
<p><strong>输出：</strong><span class="example-io">3</span></p>
|
||
|
||
<p><strong>解释：</strong></p>
|
||
|
||
<p>最好的方式是把 <code>s[2]</code> 变为除了 a 和 c 之外的东西，比如 b。然后它变成了 <code>"acbca"</code>。</p>
|
||
|
||
<p>然后我们执行以下操作：</p>
|
||
|
||
<ol>
|
||
<li>最多包含 2 个不同字符的最长前缀是 <code>"ac"</code>，我们删除它然后 <code>s</code> 变为 <code>"bca"</code>。</li>
|
||
<li>现在最多包含 2 个不同字符的最长前缀是 <code>"bc"</code>，所以我们删除它然后 <code>s</code> 变为 <code>"a"</code>。</li>
|
||
<li>最后，我们删除 <code>"a"</code> 并且 <code>s</code> 变成空串，所以该过程结束。</li>
|
||
</ol>
|
||
|
||
<p>进行操作时，字符串被分成 3 个部分，所以答案是 3。</p>
|
||
</div>
|
||
|
||
<p><strong class="example">示例 2：</strong></p>
|
||
|
||
<div class="example-block">
|
||
<p><strong>输入：</strong><span class="example-io">s = "aabaab", k = 3</span></p>
|
||
|
||
<p><strong>输出：</strong><span class="example-io">1</span></p>
|
||
|
||
<p><strong>解释：</strong></p>
|
||
|
||
<p>一开始 <code>s</code> 包含 2 个不同的字符，所以无论我们改变哪个， 它最多包含 3 个不同字符，因此最多包含 3 个不同字符的最长前缀始终是所有字符，因此答案是 1。</p>
|
||
</div>
|
||
|
||
<p><strong class="example">示例 3：</strong></p>
|
||
|
||
<div class="example-block">
|
||
<p><strong>输入：</strong><span class="example-io">s = "xxyz", k = 1</span></p>
|
||
|
||
<p><span class="example-io"><b>输出：</b>4</span></p>
|
||
|
||
<p><strong>解释：</strong></p>
|
||
|
||
<p>最好的方式是将 <code>s[0]</code> 或 <code>s[1]</code> 变为 <code>s</code> 中字符以外的东西，例如将 <code>s[0]</code> 变为 <code>w</code>。</p>
|
||
|
||
<p>然后 <code>s</code> 变为 <code>"wxyz"</code>，包含 4 个不同的字符，所以当 <code>k</code> 为 1，它将分为 4 个部分。</p>
|
||
</div>
|
||
|
||
<p> </p>
|
||
|
||
<p><strong>提示：</strong></p>
|
||
|
||
<ul>
|
||
<li><code>1 <= s.length <= 10<sup>4</sup></code></li>
|
||
<li><code>s</code> 只包含小写英文字母。</li>
|
||
<li><code>1 <= k <= 26</code></li>
|
||
</ul>
|