将字符串分成K组不同字符后的未分组字符数
给定大小为N的小写字母字符串S，以及整数K；任务是在将给定的字符串分成 K 组不同的字符后，找到将保持未分组的字符数。
示例：
输入：
S = "stayinghomesaveslife", K = 1输出：6
说明：
在字符串
S中，出现不止一次的元素为，'e'-> 3次，'s'-> 3次，'a'-> 2次，'i'-> 2次，其余所有元素出现 1 次。由于
K = 1只能生成一个基团，因此这些元素中只有一个副本存在，其余所有元素都不能在该组中。因此， 组是 2 次
'e'，2 次's'，1 次'a'和 1 次'i'。剩余元素总数为 6。
输入：
S = "stayinghomesaveslife", K = 2输出：2
说明：
在字符串
S中，出现不止一次的元素是'e'-> 3次，'s'-> 3次，'a'-> 2次，'i'-> 2次。其余所有元素出现 1 次。由于可以生成 2 个组，所以一组包含所有元素的 1 个副本。 第二组将包含 1 个额外元素的副本，即
"e"，"s"，"a"和"i"。 将被忽略的元素是 1 次"e"和 1 次"s"。剩余元素总数为 2。
方法：这个想法是使用频率计数。
-
创建一个哈希数据结构，以存储字符
"a" - "z"的频率。 -
在给定的字符串中找到每个字符的初始频率，并将其存储在哈希数据结构中。
-
由于组只能包含 1 个字符。 因此，请从散列数据结构中每个字符的出现次数减少
K。 -
现在，在哈希数据结构中添加字符的其余频率。 这将是保持未分组的所需字符数。
下面是上述方法的实现：
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
void findUngroupedElement(string s,
int k)
{
int n = s.length();
// create array where
// index represents alphabets
int b[26];
for (int i = 0; i < 26; i++)
b[i] = 0;
// fill count of every
// alphabet to corresponding
// array index
for (int i = 0; i < n; i++) {
char p = s.at(i);
b[p - 'a'] += 1;
}
int sum = 0;
// count for every element
// how much is exceeding
// from no. of groups then
// sum them
for (int i = 0; i < 26; i++) {
if (b[i] > k)
sum += b[i] - k;
}
// print answer
cout << sum << endl;
}
// Driver code
int main()
{
string s = "stayinghomesaveslife";
int k = 1;
findUngroupedElement(s, k);
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
class GFG{
static void findUngroupedElement(String s,
int k)
{
int n = s.length();
// Create array where
// index represents alphabets
int []b = new int[26];
for(int i = 0; i < 26; i++)
b[i] = 0;
// Fill count of every
// alphabet to corresponding
// array index
for(int i = 0; i < n; i++)
{
char p = s.charAt(i);
b[p - 'a'] += 1;
}
int sum = 0;
// Count for every element
// how much is exceeding
// from no. of groups then
// sum them
for(int i = 0; i < 26; i++)
{
if (b[i] > k)
sum += b[i] - k;
}
// Print answer
System.out.println(sum);
}
// Driver code
public static void main(String srgs[])
{
String s = "stayinghomesaveslife";
int k = 1;
findUngroupedElement(s, k);
}
}
// This code is contributed by ANKITKUMAR34
Python3
# Python3 code to implement the above approach
def findUngroupedElement(s, k):
n = len(s);
# Create array where
# index represents alphabets
b = [0] * 26
# Fill count of every
# alphabet to corresponding
# array index
for i in range(n):
p = s[i]
b[ord(p) - ord('a')] += 1
sum = 0;
# Count for every element
# how much is exceeding
# from no. of groups then
# sum them
for i in range(26):
if (b[i] > k):
sum += b[i] - k
# Print answer
print(sum)
# Driver code
s = "stayinghomesaveslife"
k = 1
findUngroupedElement(s, k)
# This code is contributed by ANKITKUMAR34
C
// C# code to implement the above approach
using System;
class GFG{
static void findUngroupedElement(String s,
int k)
{
int n = s.Length;
// Create array where
// index represents alphabets
int []b = new int[26];
for(int i = 0; i < 26; i++)
b[i] = 0;
// Fill count of every
// alphabet to corresponding
// array index
for(int i = 0; i < n; i++)
{
char p = s[i];
b[p - 'a'] += 1;
}
int sum = 0;
// Count for every element
// how much is exceeding
// from no. of groups then
// sum them
for(int i = 0; i < 26; i++)
{
if (b[i] > k)
sum += b[i] - k;
}
// Print answer
Console.WriteLine(sum);
}
// Driver code
public static void Main(String []srgs)
{
String s = "stayinghomesaveslife";
int k = 1;
findUngroupedElement(s, k);
}
}
// This code is contributed by Rajput-Ji
输出：
6
时间复杂度：O(n)。
辅助空间复杂度：O(26)等效于O(1)。
版权属于：月萌API www.moonapi.com，转载请注明出处
