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>
Producción:
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)