Compruebe si una string se puede dividir en dos strings con el mismo número de caracteres frecuentes K

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *