Dada una string S , la tarea es encontrar el prefijo de la string S con la máxima longitud posible de modo que la frecuencia de cada carácter en el prefijo sea como máximo el número de caracteres en S con la mínima frecuencia.
Ejemplos:
Entrada: S = ‘aabcdaab’
Salida: aabcd
Explicación:
Frecuencia de caracteres en la string dada –
{a: 4, b: 2, c: 1, d: 1}
Frecuencia mínima en 1 y el conteo de frecuencia mínima es 2,
Entonces, la frecuencia de cada carácter en el prefijo puede ser como máximo 2.Entrada: S = ‘aaabc’
Salida: aa
Explicación:
Frecuencia de caracteres en la string dada –
{a: 3, b: 1, c: 1}
Frecuencia mínima en 1 y el recuento de frecuencia mínima es 2,
por lo que la frecuencia de cada carácter en el prefijo puede ser como máximo 2.
Acercarse:
- Inicialice un mapa hash para almacenar la frecuencia de los caracteres.
- Iterar sobre la string e incrementar la frecuencia del carácter en el mapa hash.
- Encuentre el carácter mínimo ocurrido en la string y el recuento de dichos caracteres cuya frecuencia es mínima.
- Inicialice otro mapa hash para almacenar la frecuencia de los caracteres de la posible string de prefijos.
- Finalmente, itere sobre la string desde el inicio e incremente el conteo de caracteres hasta que la frecuencia de cualquier carácter no sea mayor que el conteo de la frecuencia mínima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the prefix // of the s such that occurrence of each // character is atmost the count of minimum // frequency in the s #include <bits/stdc++.h> using namespace std; // Function to find the maximum // possible prefix of the s void MaxPrefix(string s) { // Hash map to store the frequency // of the characters in the s map<char, int> Dict; // Iterate over the s to find // the occurrence of each Character for(char i : s) { Dict[i]++; } int minfrequency = INT_MAX; // Minimum frequency of the Characters for(auto x : Dict) { minfrequency = min(minfrequency, x.second); } int countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map for(auto x: Dict) { if (x.second == minfrequency) countminFrequency += 1; } map<char, int> mapper; int indi = 0; // Loop to find the maximum possible // length of the prefix in the s for(char i: s) { mapper[i] += 1; // Condition to check if the frequency // is greater than minimum possible freq if (mapper[i] > countminFrequency) break; indi += 1; } // maxprefix s and its length. cout << (s.substr(0, indi)); } // Driver code int main() { // s is initialize. string str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str); } // This code is contributed by mohit kumar 29
Java
// Java implementation to find the prefix // of the s such that occurrence of each // character is atmost the count of minimum // frequency in the s import java.util.*; import java.lang.*; import java.io.*; class GFG{ // Function to find the maximum // possible prefix of the s static void MaxPrefix(String s) { // Hash map to store the frequency // of the characters in the s Map<Character, Integer> Dict = new HashMap<>(); // Iterate over the s to find // the occurrence of each Character for(char i : s.toCharArray()) { Dict.put(i, Dict.getOrDefault(i, 0) + 1); } int minfrequency = Integer.MAX_VALUE; // Minimum frequency of the Characters for(Integer x: Dict.values()) { minfrequency = Math.min(minfrequency, x); } int countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map for(Map.Entry<Character, Integer> x: Dict.entrySet()) { if (x.getValue() == minfrequency) countminFrequency += 1; } Map<Character, Integer> mapper = new HashMap<>(); int indi = 0; // Loop to find the maximum possible // length of the prefix in the s for(char i: s.toCharArray()) { mapper.put(i, mapper.getOrDefault(i, 0) + 1); // Condition to check if the frequency // is greater than minimum possible freq if (mapper.get(i) > countminFrequency) break; indi += 1; } // maxprefix s and its length. System.out.println(s.substring(0, indi)); } // Driver code public static void main(String[] args) { // s is initialize. String str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str); } } // This code is contributed by offbeat
Python3
# Python3 implementation to find the # prefix of the string such that # occurrence of each character is # atmost the count of minimum # frequency in the string # Function to find the maximum # possible prefix of the string def MaxPrefix(string): # Hash map to store the frequency # of the characters in the string Dict = {} maxprefix = 0 # Iterate over the string to find # the occurrence of each Character for i in string: Dict[i] = Dict.get(i, 0) + 1 # Minimum frequency of the Characters minfrequency = min(Dict.values()) countminFrequency = 0 # Loop to find the count of minimum # frequency in the hash-map for x in Dict: if (Dict[x] == minfrequency): countminFrequency += 1 mapper = {} indi = 0 # Loop to find the maximum possible # length of the prefix in the string for i in string: mapper[i] = mapper.get(i, 0) + 1 # Condition to check if the frequency # is greater than minimum possible freq if (mapper[i] > countminFrequency): break indi += 1 # maxprefix string and its length. print(string[:indi]) # Driver code if __name__ == '__main__': # String is initialize. str = 'aabcdaab' # str is passed in MaxPrefix function. MaxPrefix(str)
C#
// C# implementation to find the // prefix of the s such that // occurrence of each character is // atmost the count of minimum // frequency in the s using System; using System.Collections; using System.Collections.Generic; using System.Linq; class GFG{ // Function to find the maximum // possible prefix of the s static void MaxPrefix(string s) { // Hash map to store the frequency // of the characters in the s Dictionary<char, int> Dict = new Dictionary<char, int>(); // Iterate over the s to find // the occurrence of each Character foreach(char i in s) { if (Dict.ContainsKey(i)) { Dict[i]++; } else { Dict[i] = 1; } } int minfrequency = Int32.MaxValue; // Minimum frequency of the Characters foreach(int x in Dict.Values.ToList()) { minfrequency = Math.Min(minfrequency, x); } int countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map foreach(char x in Dict.Keys.ToList()) { if (Dict[x] == minfrequency) countminFrequency += 1; } Dictionary<char, int> mapper = new Dictionary<char, int>(); int indi = 0; // Loop to find the maximum possible // length of the prefix in the s foreach(char i in s) { if (mapper.ContainsKey(i)) { mapper[i]++; } else { mapper[i] = 1; } // Condition to check if the frequency // is greater than minimum possible freq if (mapper[i] > countminFrequency) break; indi += 1; } // maxprefix s and its length. Console.Write(s.Substring(0, indi)); } // Driver Code public static void Main(string[] args) { // s is initialize. string str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str); } } // This code is contributed by rutvik_56
Javascript
<script> // JavaScript implementation to find the // prefix of the s such that // occurrence of each character is // atmost the count of minimum // frequency in the s // Function to find the maximum // possible prefix of the s function MaxPrefix(s) { // Hash map to store the frequency // of the characters in the s var Dict = {}; // Iterate over the s to find // the occurrence of each Character for (const i of s) { if (Dict.hasOwnProperty(i)) { Dict[i]++; } else { Dict[i] = 1; } } var minfrequency = 2147483647; // Minimum frequency of the Characters for (const [key, value] of Object.entries(Dict)) { minfrequency = Math.min(minfrequency, value); } var countminFrequency = 0; // Loop to find the count of minimum // frequency in the hash-map for (const [key, value] of Object.entries(Dict)) { if (Dict[key] === minfrequency) countminFrequency += 1; } var mapper = {}; var indi = 0; // Loop to find the maximum possible // length of the prefix in the s for (const i of s) { if (mapper.hasOwnProperty(i)) { mapper[i]++; } else { mapper[i] = 1; } // Condition to check if the frequency // is greater than minimum possible freq if (mapper[i] > countminFrequency) break; indi += 1; } // maxprefix s and its length. document.write(s.substring(0, indi)); } // Driver Code // s is initialize. var str = "aabcdaab"; // str is passed in // MaxPrefix function. MaxPrefix(str); </script>
aabcd
Análisis de rendimiento:
- Complejidad de tiempo: en el enfoque anterior, hay un ciclo para encontrar la frecuencia de cada carácter en la string que toma el tiempo O (N) en el peor de los casos. Por lo tanto, la complejidad temporal para este enfoque será O(N) .
- Complejidad espacial: en el enfoque anterior, se utiliza espacio adicional para almacenar la frecuencia de los caracteres. Por lo tanto, la complejidad del espacio para el enfoque anterior será O(N)