minimum-deletions-for-at-most-k-distinct-characters

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a string <code>s</code> consisting of lowercase English letters, and an integer <code>k</code>.

Your task is to delete some (possibly none) of the characters in the string so that the number of distinct characters in the resulting string is at most <code>k</code>.

Return the minimum number of deletions required to achieve this.

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;abc&quot;, k = 2

Output: 1

Explanation:

<ul>
	<li><code>s</code> has three distinct characters: <code>&#39;a&#39;</code>, <code>&#39;b&#39;</code> and <code>&#39;c&#39;</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>&#39;c&#39;</code> results in at most <code>k</code> distinct characters. Thus, the answer is 1.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: s = &quot;aabb&quot;, k = 2

Output: 0

Explanation:

<ul>
	<li><code>s</code> has two distinct characters (<code>&#39;a&#39;</code> and <code>&#39;b&#39;</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>

Example 3:

<div class="example-block">
Input: s = &quot;yyyzz&quot;, k = 1

Output: 2

Explanation:

<ul>
	<li><code>s</code> has two distinct characters (<code>&#39;y&#39;</code> and <code>&#39;z&#39;</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>&#39;z&#39;</code> results in at most <code>k</code> distinct characters. Thus, the answer is 2.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 16</code></li>
	<li><code>1 &lt;= k &lt;= 16</code></li>
	<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

第 449 场周赛

weekly-contest-449

minDeletion

中级工程师

Minimum Deletions for At Most K Distinct Characters

Greedy

Hash Table

String

Counting

Sorting

给你一个字符串 <code>s</code>（由小写英文字母组成）和一个整数 <code>k</code>。

你的任务是删除字符串中的一些字符（可以不删除任何字符），使得结果字符串中的&nbsp;不同字符数量&nbsp;最多为 <code>k</code>。

返回为达到上述目标所需删除的&nbsp;最小&nbsp;字符数量。

&nbsp;

示例 1：

<div class="example-block">
输入： s = "abc", k = 2

输出： 1

解释：

<ul>
	<li><code>s</code> 有三个不同的字符：<code>'a'</code>、<code>'b'</code> 和 <code>'c'</code>，每个字符的出现频率为 1。</li>
	<li>由于最多只能有 <code>k = 2</code> 个不同字符，需要删除某一个字符的所有出现。</li>
	<li>例如，删除所有 <code>'c'</code> 后，结果字符串中的不同字符数最多为 <code>k</code>。因此，答案是 1。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： s = "aabb", k = 2

输出： 0

解释：

<ul>
	<li><code>s</code> 有两个不同的字符（<code>'a'</code> 和 <code>'b'</code>），它们的出现频率分别为 2 和 2。</li>
	<li>由于最多可以有 <code>k = 2</code> 个不同字符，不需要删除任何字符。因此，答案是 0。</li>
</ul>
</div>

示例 3：

<div class="example-block">
输入： s = "yyyzz", k = 1

输出： 2

解释：

<ul>
	<li><code>s</code> 有两个不同的字符（<code>'y'</code> 和 <code>'z'</code>），它们的出现频率分别为 3 和 2。</li>
	<li>由于最多只能有 <code>k = 1</code> 个不同字符，需要删除某一个字符的所有出现。</li>
	<li>删除所有 <code>'z'</code> 后，结果字符串中的不同字符数最多为 <code>k</code>。因此，答案是 2。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 16</code></li>
	<li><code>1 &lt;= k &lt;= 16</code></li>
	<li><code>s</code> 仅由小写英文字母组成。</li>
</ul>

&nbsp;