mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-09-05 15:31:43 +08:00
65 lines
2.6 KiB
HTML
65 lines
2.6 KiB
HTML
<p>You are given a string <code>s</code> consisting of lowercase English letters, and an integer <code>k</code>.</p>
|
|
|
|
<p>Your task is to delete some (possibly none) of the characters in the string so that the number of <strong>distinct</strong> characters in the resulting string is <strong>at most</strong> <code>k</code>.</p>
|
|
|
|
<p>Return the <strong>minimum</strong> number of deletions required to achieve this.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">s = "abc", k = 2</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">1</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>s</code> has three distinct characters: <code>'a'</code>, <code>'b'</code> and <code>'c'</code>, each with a frequency of 1.</li>
|
|
<li>Since we can have at most <code>k = 2</code> distinct characters, remove all occurrences of any one character from the string.</li>
|
|
<li>For example, removing all occurrences of <code>'c'</code> results in at most <code>k</code> distinct characters. Thus, the answer is 1.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">s = "aabb", k = 2</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">0</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>s</code> has two distinct characters (<code>'a'</code> and <code>'b'</code>) with frequencies of 2 and 2, respectively.</li>
|
|
<li>Since we can have at most <code>k = 2</code> distinct characters, no deletions are required. Thus, the answer is 0.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">s = "yyyzz", k = 1</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">2</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>s</code> has two distinct characters (<code>'y'</code> and <code>'z'</code>) with frequencies of 3 and 2, respectively.</li>
|
|
<li>Since we can have at most <code>k = 1</code> distinct character, remove all occurrences of any one character from the string.</li>
|
|
<li>Removing all <code>'z'</code> results in at most <code>k</code> distinct characters. Thus, the answer is 2.</li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= s.length <= 16</code></li>
|
|
<li><code>1 <= k <= 16</code></li>
|
|
<li><code>s</code> consists only of lowercase English letters.</li>
|
|
</ul>
|
|
|
|
<p> </p>
|