Número de posiciones para dividir la string de modo que al menos m caracteres con la misma frecuencia estén presentes en cada substring

Dada una string str de alfabetos ingleses en minúsculas y un entero m . La tarea es contar cuántas posiciones hay en la string de modo que si divide la string en dos substrings no vacías, hay al menos m caracteres con la misma frecuencia en ambas substrings. 
Los caracteres deben estar presentes en la string str .
Ejemplos: 
 

Entrada: str = “aabbccaa”, m = 2 
Salida:
La string tiene una longitud de 8, por lo que hay 7 posiciones disponibles para realizar la partición. 
es decir, a|a|b|b|c|c|a|a 
Sólo son posibles dos particiones que satisfagan las restricciones dadas. 
aab|bccaa: en la mitad izquierda del separador, ‘a’ tiene la frecuencia 2 y ‘b’ tiene la frecuencia 1, 
que es la misma que la de la mitad derecha. 
aabbc|caa: en la mitad izquierda del separador, ‘a’ tiene una frecuencia de 2 y ‘c’ tiene una frecuencia de 1, 
que es la misma que la de la mitad derecha.
Entrada: str = “aabbaa”, m = 2 
Salida:
 

Enfoque: para cada posición de partición, calcule las frecuencias de cada uno de los caracteres de la string en ambas particiones. Luego calcule la cantidad de caracteres que tienen la misma frecuencia en ambas particiones. Si el recuento de dichos caracteres es al menos m, agregue 1 al recuento requerido de particiones.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of ways
// to partition the given so that the
// given condition is satisfied
int countWays(string str, int m)
{
    // Hashset to store unique characters
    // in the given string
    set<char> s;
    for (int i = 0; i < str.length(); i++)
        s.insert(str[i]);
 
    // To store the number of ways
    // to partition the string
    int result = 0;
 
    for (int i = 1; i < str.length(); i++)
    {
        // Hashmaps to store frequency of characters
        // of both the partitions
        map<char, int> first_map, second_map;
 
        // Iterate in the first partition
        for (int j = 0; j < i; j++)
 
            // If character already exists in the hashmap
            // then increase it's frequency
            first_map[str[j]]++;
 
        // Iterate in the second partition
        for (int k = 0; k < str.length(); k++)
 
            // If character already exists in the hashmap
            // then increase it's frequency
            second_map[str[k]]++;
 
        // Iterator for HashSet
        set<char>::iterator itr = s.begin();
 
        // To store the count of characters that have
        // equal frequencies in both the partitions
        int total_count = 0;
        while (++itr != s.end())
        {
            // first_count and second_count keeps track
            // of the frequencies of each character
            int first_count = 0, second_count = 0;
            char ch = *(itr);
 
            // Frequency of the character
            // in the first partition
            if (first_map.find(ch) != first_map.end())
                first_count = first_map[ch];
 
            // Frequency of the character
            // in the second partition
            if (second_map.find(ch) != second_map.end())
                second_count = second_map[ch];
 
            // Check if frequency is same
            // in both the partitions
            if (first_count == second_count &&
                first_count != 0)
                total_count += 1;
        }
 
        // Check if the condition is satisfied
        // for the current partition
        if (total_count >= m)
            result += 1;
    }
    return result;
}
 
// Driver code
int main(int argc, char const *argv[])
{
    string str = "aabbccaa";
    int m = 2;
    cout << countWays(str, m) << endl;
    return 0;
}
 
// This code is contributed by
// sanjeev2552

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    // Function to return the number of ways
    // to partition the given so that the
    // given condition is satisfied
    static int countWays(String str, int m)
    {
 
        // Hashset to store unique characters
        // in the given string
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < str.length(); i++)
            set.add(str.charAt(i));
 
        // To store the number of ways
        // to partition the string
        int result = 0;
 
        for (int i = 1; i < str.length(); i++) {
 
            // Hashmaps to store frequency of characters
            // of both the partitions
            HashMap<Character, Integer> first_map
                = new HashMap<Character, Integer>();
            HashMap<Character, Integer> second_map
                = new HashMap<Character, Integer>();
 
            // Iterate in the first partition
            for (int j = 0; j < i; j++) {
 
                // If character already exists in the hashmap
                // then increase it's frequency
                if (first_map.containsKey(str.charAt(j)))
                    first_map.put(str.charAt(j),
                                  (first_map.get(str.charAt(j)) + 1));
 
                // Else create an entry for it in the Hashmap
                else
                    first_map.put(str.charAt(j), 1);
            }
 
            // Iterate in the second partition
            for (int k = i; k < str.length(); k++) {
 
                // If character already exists in the hashmap
                // then increase it's frequency
                if (second_map.containsKey(str.charAt(k)))
                    second_map.put(str.charAt(k),
                                   (second_map.get(str.charAt(k)) + 1));
 
                // Else create an entry for it in the Hashmap
                else
                    second_map.put(str.charAt(k), 1);
            }
 
            // Iterator for HashSet
            Iterator itr = set.iterator();
 
            // To store the count of characters that have
            // equal frequencies in both the partitions
            int total_count = 0;
 
            while (itr.hasNext()) {
 
                // first_count and second_count keeps track
                // of the frequencies of each character
                int first_count = 0, second_count = 0;
                char ch = (char)itr.next();
 
                // Frequency of the character
                // in the first partition
                if (first_map.containsKey(ch))
                    first_count = first_map.get(ch);
 
                // Frequency of the character
                // in the second partition
                if (second_map.containsKey(ch))
                    second_count = second_map.get(ch);
 
                // Check if frequency is same in both the partitions
                if (first_count == second_count && first_count != 0)
                    total_count += 1;
            }
 
            // Check if the condition is satisfied
            // for the current partition
            if (total_count >= m)
                result += 1;
        }
 
        return result;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String str = "aabbccaa";
        int m = 2;
        System.out.println(countWays(str, m));
    }
}

Python3

# Python3 implementation of the approach
from collections import defaultdict
 
# Function to return the number of ways
# to partition the given so that the
# given condition is satisfied
def countWays(string, m):
 
    # Hashset to store unique
    # characters in the given string
    Set = set()
    for i in range(0, len(string)):
        Set.add(string[i])
 
    # To store the number of ways
    # to partition the string
    result = 0
 
    for i in range(1, len(string)):
 
        # Hashmaps to store frequency of
        # characters of both the partitions
        first_map = defaultdict(lambda:0)
        second_map = defaultdict(lambda:0)
 
        # Iterate in the first partition
        for j in range(0, i):
 
            first_map[string[j]] += 1
         
        # Iterate in the second partition
        for k in range(i, len(string)):
 
            second_map[string[k]] += 1
         
        # To store the count of characters that have
        # equal frequencies in both the partitions
        total_count = 0
 
        for ch in Set:
 
            # first_count and second_count keeps track
            # of the frequencies of each character
            first_count, second_count = 0, 0
 
            # Frequency of the character
            # in the first partition
            if ch in first_map:
                first_count = first_map[ch]
 
            # Frequency of the character
            # in the second partition
            if ch in second_map:
                second_count = second_map[ch]
 
            # Check if frequency is same in both the partitions
            if first_count == second_count and first_count != 0:
                total_count += 1
         
        # Check if the condition is satisfied
        # for the current partition
        if total_count >= m:
            result += 1
     
    return result
 
# Driver code
if __name__ == "__main__":
 
    string = "aabbccaa"
    m = 2
    print(countWays(string, m))
     
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
public class GFG {
  
    // Function to return the number of ways
    // to partition the given so that the
    // given condition is satisfied
    static int countWays(String str, int m)
    {
  
        // Hashset to store unique characters
        // in the given string
        HashSet<char> set = new HashSet<char>();
        for (int i = 0; i < str.Length; i++)
            set.Add(str[i]);
  
        // To store the number of ways
        // to partition the string
        int result = 0;
  
        for (int i = 1; i < str.Length; i++) {
  
            // Hashmaps to store frequency of characters
            // of both the partitions
            Dictionary<char, int> first_map
                = new Dictionary<char, int>();
            Dictionary<char, int> second_map
                = new Dictionary<char, int>();
  
            // Iterate in the first partition
            for (int j = 0; j < i; j++) {
  
                // If character already exists in the hashmap
                // then increase it's frequency
                if (first_map.ContainsKey(str[j]))
                    first_map[str[j]] =
                                  (first_map[str[j]] + 1);
  
                // Else create an entry for it in the Hashmap
                else
                    first_map.Add(str[j], 1);
            }
  
            // Iterate in the second partition
            for (int k = i; k < str.Length; k++) {
  
                // If character already exists in the hashmap
                // then increase it's frequency
                if (second_map.ContainsKey(str[k]))
                    second_map[str[k]] =
                                   (second_map[str[k]] + 1);
  
                // Else create an entry for it in the Hashmap
                else
                    second_map.Add(str[k], 1);
            }
  
  
            // To store the count of characters that have
            // equal frequencies in both the partitions
            int total_count = 0;
             // Iterator for HashSet
            foreach (int itr in set) {
  
                // first_count and second_count keeps track
                // of the frequencies of each character
                int first_count = 0, second_count = 0;
                char ch = (char)itr;
  
                // Frequency of the character
                // in the first partition
                if (first_map.ContainsKey(ch))
                    first_count = first_map[ch];
  
                // Frequency of the character
                // in the second partition
                if (second_map.ContainsKey(ch))
                    second_count = second_map[ch];
  
                // Check if frequency is same in both the partitions
                if (first_count == second_count && first_count != 0)
                    total_count += 1;
            }
  
            // Check if the condition is satisfied
            // for the current partition
            if (total_count >= m)
                result += 1;
        }
  
        return result;
    }
  
    // Driver code
    public static void Main(String[] args)
    {
        String str = "aabbccaa";
        int m = 2;
        Console.WriteLine(countWays(str, m));
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the number of ways
// to partition the given so that the
// given condition is satisfied
function countWays(str, m)
{
    // Hashset to store unique characters
    // in the given string
    var s = new Set();
    for (var i = 0; i < str.length; i++)
        s.add(str[i]);
 
    // To store the number of ways
    // to partition the string
    var result = 0;
 
    for (var i = 1; i < str.length; i++)
    {
        // Hashmaps to store frequency of characters
        // of both the partitions
        var first_map = new Map(), second_map = new Map();
 
        // Iterate in the first partition
        for (var j = 0; j < i; j++)
 
            // If character already exists in the hashmap
            // then increase it's frequency
            if(first_map.has(str[j]))
                first_map.set(str[j], first_map.get(str[j])+1)
            else
                first_map.set(str[j], 1)
 
        // Iterate in the second partition
        for (var k = 0; k < str.length; k++)
 
            // If character already exists in the hashmap
            // then increase it's frequency
            if(second_map.has(str[k]))
                second_map.set(str[k], second_map.get(str[k])+1)
            else
                second_map.set(str[k], 1)
 
 
        // To store the count of characters that have
        // equal frequencies in both the partitions
        var total_count = 0;
        s.forEach(itr => {
             
            // first_count and second_count keeps track
            // of the frequencies of each character
            var first_count = 0, second_count = 0;
            var ch = itr;
 
            // Frequency of the character
            // in the first partition
            if (first_map.has(ch))
                first_count = first_map.get(ch);
 
            // Frequency of the character
            // in the second partition
            if (second_map.has(ch))
                second_count = second_map.get(ch);
 
            // Check if frequency is same
            // in both the partitions
            if (first_count == second_count &&
                first_count != 0)
                total_count += 1;
        });
 
        // Check if the condition is satisfied
        // for the current partition
        if (total_count >= m)
            result += 1;
    }
    return result;
}
 
// Driver code
var str = "aabbccaa";
var m = 2;
document.write( countWays(str, m));
 
// This code is contributed by itsok.
</script>
Producción: 

2

 

Complejidad de tiempo: O(n*n*log(n)), ya que los bucles anidados se utilizan para la iteración
Espacio auxiliar: O(n), ya que el espacio adicional de tamaño n se utiliza para crear un conjunto y un mapa

Publicación traducida automáticamente

Artículo escrito por Divyank_Sheth 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 *