Dada una string S y un entero K , la tarea es verificar si es posible distribuir estos caracteres en dos strings de modo que la cantidad de caracteres que tienen una frecuencia K en ambas strings sea igual.
Si es posible, imprima una secuencia que consta de 1 y 2 , que indica qué carácter debe colocarse en qué string. De lo contrario, imprima NO .
Nota: una de estas nuevas strings puede estar vacía.
Ejemplos:
Entrada: S = “abbbccc”, K = 1
Salida: 1111211
Explicación:
Las dos strings son “abbbcc” y “c”.
Por lo tanto, ambas strings tienen exactamente 1 carácter con frecuencia K( = 1).Entrada: S = “aaaa”, K = 3
Salida: 1111
Explicación:
las strings se pueden dividir en “aaaa” y “”.
Por lo tanto, ningún carácter tiene frecuencia 3 en ambas strings.
Enfoque:
siga los pasos a continuación para resolver el problema:
- Verifique las siguientes tres condiciones para determinar si una división es posible o no:
1. Si el número total de caracteres que tienen una frecuencia K en la string inicial es par , entonces estos caracteres se pueden colocar igualmente en dos strings y el resto de la Los caracteres (que tienen una frecuencia diferente a K ) se pueden colocar en cualquiera de los dos grupos.
2. Si el número total de caracteres que tienen una frecuencia K en la string inicial es impar , entonces si hay un carácter en la string inicial que tiene una frecuencia mayor que K pero no igual a 2K , entonces esa distribución es posible.
Ilustración:
S =”abceeee”, K = 1
Dividir en “abeee” y “ce”. Por lo tanto, ambas strings tienen 2 caracteres con frecuencia 1.
3. Si el número total de caracteres que tienen una frecuencia K en la string inicial es impar , entonces si hay un carácter en la string inicial que tiene una frecuencia igual a 2K , entonces tal distribución es posible.
Ilustración:
S =”aaaabbccdde”, K = 2
Dividir en “aabbc” y “aaddce” para que ambas strings tengan dos caracteres con frecuencia 2.
- Si las tres condiciones mencionadas anteriormente fallan, entonces la respuesta es «NO» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the
// arrangement of characters
void DivideString(string s, int n,
int k)
{
int i, c = 0, no = 1;
int c1 = 0, c2 = 0;
// Stores frequency of
// characters
int fr[26] = { 0 };
string ans = "";
for (i = 0; i < n; i++) {
fr[s[i] - 'a']++;
}
char ch, ch1;
for (i = 0; i < 26; i++) {
// Count the character
// having frequency K
if (fr[i] == k) {
c++;
}
// Count the character
// having frequency
// greater than K and
// not equal to 2K
if (fr[i] > k
&& fr[i] != 2 * k) {
c1++;
ch = i + 'a';
}
if (fr[i] == 2 * k) {
c2++;
ch1 = i + 'a';
}
}
for (i = 0; i < n; i++)
ans = ans + "1";
map<char, int> mp;
if (c % 2 == 0 || c1 > 0 || c2 > 0) {
for (i = 0; i < n; i++) {
// Case 1
if (fr[s[i] - 'a'] == k) {
if (mp.find(s[i])
!= mp.end()) {
ans[i] = '2';
}
else {
if (no <= (c / 2)) {
ans[i] = '2';
no++;
mp[s[i]] = 1;
}
}
}
}
// Case 2
if (c % 2 == 1 && c1 > 0) {
no = 1;
for (i = 0; i < n; i++) {
if (s[i] == ch && no <= k) {
ans[i] = '2';
no++;
}
}
}
// Case 3
if (c % 2 == 1 && c1 == 0) {
no = 1;
int flag = 0;
for (int i = 0; i < n; i++) {
if (s[i] == ch1 && no <= k) {
ans[i] = '2';
no++;
}
if (fr[s[i] - 'a'] == k
&& flag == 0
&& ans[i] == '1') {
ans[i] = '2';
flag = 1;
}
}
}
cout << ans << endl;
}
else {
// If all cases fail
cout << "NO" << endl;
}
}
// Driver Code
int main()
{
string S = "abbbccc";
int N = S.size();
int K = 1;
DivideString(S, N, K);
return 0;
}
Java
// Java program for the above problem
import java.util.*;
class GFG{
// Function to print the
// arrangement of characters
public static void DivideString(String s, int n,
int k)
{
int i, c = 0, no = 1;
int c1 = 0, c2 = 0;
// Stores frequency of
// characters
int[] fr = new int[26];
char[] ans = new char[n];
for(i = 0; i < n; i++)
{
fr[s.charAt(i) - 'a']++;
}
char ch = 'a', ch1 = 'a';
for(i = 0; i < 26; i++)
{
// Count the character
// having frequency K
if (fr[i] == k)
{
c++;
}
// Count the character
// having frequency
// greater than K and
// not equal to 2K
if (fr[i] > k && fr[i] != 2 * k)
{
c1++;
ch = (char)(i + 'a');
}
if (fr[i] == 2 * k)
{
c2++;
ch1 = (char)(i + 'a');
}
}
for(i = 0; i < n; i++)
ans[i] = '1';
HashMap<Character, Integer> mp = new HashMap<>();
if (c % 2 == 0 || c1 > 0 || c2 > 0)
{
for(i = 0; i < n; i++)
{
// Case 1
if (fr[s.charAt(i) - 'a'] == k)
{
if (mp.containsKey(s.charAt(i)))
{
ans[i] = '2';
}
else
{
if (no <= (c / 2))
{
ans[i] = '2';
no++;
mp.replace(s.charAt(i), 1);
}
}
}
}
// Case 2
if ( (c % 2 == 1) && (c1 > 0) )
{
no = 1;
for(i = 0; i < n; i++)
{
if (s.charAt(i) == ch && no <= k)
{
ans[i] = '2';
no++;
}
}
}
// Case 3
if (c % 2 == 1 && c1 == 0)
{
no = 1;
int flag = 0;
for(i = 0; i < n; i++)
{
if (s.charAt(i) == ch1 && no <= k)
{
ans[i] = '2';
no++;
}
if (fr[s.charAt(i) - 'a'] == k &&
flag == 0 && ans[i] == '1')
{
ans[i] = '2';
flag = 1;
}
}
}
System.out.println(ans);
}
else
{
// If all cases fail
System.out.println("NO");
}
}
// Driver code
public static void main(String[] args)
{
String S = "abbbccc";
int N = S.length();
int K = 1;
DivideString(S, N, K);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation of the
# above approach
# Function to print the
# arrangement of characters
def DivideString(s, n, k):
c = 0
no = 1
c1 = 0
c2 = 0
# Stores frequency of
# characters
fr = [0] * 26
ans = []
for i in range(n):
fr[ord(s[i]) - ord('a')] += 1
for i in range(26):
# Count the character
# having frequency K
if (fr[i] == k):
c += 1
# Count the character having
# frequency greater than K and
# not equal to 2K
if (fr[i] > k and fr[i] != 2 * k):
c1 += 1
ch = chr(ord('a') + i)
if (fr[i] == 2 * k):
c2 += 1
ch1 = chr(ord('a') + i)
for i in range(n):
ans.append("1")
mp = {}
if (c % 2 == 0 or c1 > 0 or c2 > 0):
for i in range(n):
# Case 1
if (fr[ord(s[i]) - ord('a')] == k):
if (s[i] in mp):
ans[i] = '2'
else:
if (no <= (c // 2)):
ans[i] = '2'
no += 1
mp[s[i]] = 1
# Case 2
if (c % 2 == 1 and c1 > 0):
no = 1
for i in range(n):
if (s[i] == ch and no <= k):
ans[i] = '2'
no += 1
# Case 3
if (c % 2 == 1 and c1 == 0):
no = 1
flag = 0
for i in range(n):
if (s[i] == ch1 and no <= k):
ans[i] = '2'
no += 1
if (fr[s[i] - 'a'] == k and
flag == 0 and
ans[i] == '1'):
ans[i] = '2'
flag = 1
print("".join(ans))
else:
# If all cases fail
print("NO")
# Driver Code
if __name__ == '__main__':
S = "abbbccc"
N = len(S)
K = 1
DivideString(S, N, K)
# This code is contributed by mohit kumar 29
C#
// C# program for the above problem
using System;
using System.Collections.Generic;
class GFG{
// Function to print the
// arrangement of characters
public static void DivideString(string s, int n,
int k)
{
int i, c = 0, no = 1;
int c1 = 0, c2 = 0;
// Stores frequency of
// characters
int[] fr = new int[26];
char[] ans = new char[n];
for(i = 0; i < n; i++)
{
fr[s[i] - 'a']++;
}
char ch = 'a', ch1 = 'a';
for(i = 0; i < 26; i++)
{
// Count the character
// having frequency K
if (fr[i] == k)
{
c++;
}
// Count the character having
// frequency greater than K and
// not equal to 2K
if (fr[i] > k && fr[i] != 2 * k)
{
c1++;
ch = (char)(i + 'a');
}
if (fr[i] == 2 * k)
{
c2++;
ch1 = (char)(i + 'a');
}
}
for(i = 0; i < n; i++)
ans[i] = '1';
Dictionary<char,
int> mp = new Dictionary<char,
int>();
if (c % 2 == 0 || c1 > 0 || c2 > 0)
{
for(i = 0; i < n; i++)
{
// Case 1
if (fr[s[i] - 'a'] == k)
{
if (mp.ContainsKey(s[i]))
{
ans[i] = '2';
}
else
{
if (no <= (c / 2))
{
ans[i] = '2';
no++;
mp[s[i]] = 1;
}
}
}
}
// Case 2
if ( (c % 2 == 1) && (c1 > 0) )
{
no = 1;
for(i = 0; i < n; i++)
{
if (s[i]== ch && no <= k)
{
ans[i] = '2';
no++;
}
}
}
// Case 3
if (c % 2 == 1 && c1 == 0)
{
no = 1;
int flag = 0;
for(i = 0; i < n; i++)
{
if (s[i] == ch1 && no <= k)
{
ans[i] = '2';
no++;
}
if (fr[s[i] - 'a'] == k &&
flag == 0 && ans[i] == '1')
{
ans[i] = '2';
flag = 1;
}
}
}
Console.Write(ans);
}
else
{
// If all cases fail
Console.Write("NO");
}
}
// Driver code
public static void Main(string[] args)
{
string S = "abbbccc";
int N = S.Length;
int K = 1;
DivideString(S, N, K);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program for the above problem
// Function to print the
// arrangement of characters
function DivideString(s, n, k) {
var i,
c = 0,
no = 1;
var c1 = 0,
c2 = 0;
// Stores frequency of
// characters
var fr = new Array(26).fill(0);
var ans = [];
for (i = 0; i < n; i++) {
fr[s[i].charCodeAt(0) - "a".charCodeAt(0)]++;
}
var ch = "a",
ch1 = "a";
for (i = 0; i < 26; i++) {
// Count the character
// having frequency K
if (fr[i] === k) {
c++;
}
// Count the character having
// frequency greater than K and
// not equal to 2K
if (fr[i] > k && fr[i] !== 2 * k) {
c1++;
ch = String.fromCharCode(i + "a".charCodeAt(0));
}
if (fr[i] === 2 * k) {
c2++;
ch1 = String.fromCharCode(i + "a".charCodeAt(0));
}
}
for (i = 0; i < n; i++) ans.push("1");
var mp = {};
if (c % 2 === 0 || c1 > 0 || c2 > 0) {
for (i = 0; i < n; i++) {
// Case 1
if (fr[s[i].charCodeAt(0) - "a".charCodeAt(0)] === k) {
if (mp.hasOwnProperty(s[i])) {
ans[i] = "2";
}
else {
if (no <= parseInt(c / 2)) {
ans[i] = "2";
no++;
mp[s[i]] = 1;
}
}
}
}
// Case 2
if (c % 2 === 1 && c1 > 0) {
no = 1;
for (i = 0; i < n; i++) {
if (s[i] === ch && no <= k) {
ans[i] = "2";
no++;
}
}
}
// Case 3
if (c % 2 === 1 && c1 === 0) {
no = 1;
var flag = 0;
for (i = 0; i < n; i++) {
if (s[i] === ch1 && no <= k) {
ans[i] = "2";
no++;
}
if (
fr[s[i].charCodeAt(0) - "a".charCodeAt(0)] === k &&
flag === 0 &&
ans[i] === "1"
) {
ans[i] = "2";
flag = 1;
}
}
}
document.write(ans.join(""));
}
else {
// If all cases fail
document.write("NO");
}
}
// Driver code
var S = "abbbccc";
var N = S.length;
var K = 1;
DivideString(S, N, K);
</script>
Producción:
1111211
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por AyanChowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA