Dada una array arr[] de N enteros, la tarea es encontrar la longitud máxima del prefijo de la array de modo que al eliminar exactamente un elemento del prefijo, la frecuencia de los elementos restantes del prefijo sea la misma.
Ejemplos:
Entrada: arr[] = {1, 1, 1, 2, 2, 2}
Salida: 5
Explicación:
Los siguientes prefijos cumplen las condiciones dadas:
- El prefijo sobre el rango [0, 0]. Eliminar el único elemento en el prefijo quedará vacío.
- El prefijo sobre el rango [0, 1]. Al eliminar cualquiera de los elementos del prefijo, la frecuencia de cada elemento será igual en el prefijo.
- El prefijo sobre el rango [0, 2]. Al eliminar cualquiera de los elementos del prefijo, la frecuencia de cada elemento será igual en el prefijo.
- El prefijo sobre el rango [0, 3]. Al eliminar el elemento en el índice 3 del prefijo, la frecuencia de cada elemento será igual en el prefijo.
- El prefijo sobre el rango [0, 4]. Al eliminar cualquier elemento en el rango [0, 2] del prefijo, la frecuencia de cada elemento será igual en el prefijo.
Por lo tanto, la longitud máxima del prefijo que cumple las condiciones es 5.
Entrada: arr[] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5}
Salida: 13
El enfoque basado en hashing y clasificación se ha discutido en el Conjunto 1 de este artículo.
Enfoque: La idea es usar dos mapas para realizar un seguimiento de las frecuencias de los elementos y usar las siguientes cuatro condiciones para verificar los prefijos válidos.
- Las frecuencias de todos los elementos del prefijo son iguales a 1.
- Todos los elementos de la ventana de prefijos son iguales.
- Existen solo dos frecuencias distintas de los elementos en el prefijo y la diferencia entre ellas es igual a 1 y el recuento de la frecuencia con un valor mayor es 1.
- Existe un solo elemento con frecuencia 1 y excepto que todos los elementos tienen la misma frecuencia.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos mapas , digamos mp1 y mp2 para almacenar la frecuencia de los elementos en el prefijo y para almacenar la frecuencia de las frecuencias de los elementos respectivamente.
- Además, inicialice una variable, digamos ans como 0 para almacenar la longitud máxima del prefijo.
- Recorra el rango [0, N-1] usando la variable i y siga los pasos a continuación:
- Si el conteo de arr[i] no es igual a 0 , entonces disminuya el conteo de esa frecuencia del mapa mp2 y si se vuelve 0 , entonces borre el valor del mapa mp2.
- Incremente el recuento de arr[i] en el mapa mp1 en 1 y luego incremente el recuento de la nueva frecuencia de arr[i], es decir , mp1[arr[i]] en el mapa mp2 en 1.
- Si el conteo del elemento actual es igual a la longitud de su prefijo, es decir (i+1 ) o cada elemento ocurrió una vez en el prefijo, actualice el valor de ans a max(ans, i+1) .
- Ahora, si el tamaño de mp2 es igual a 2 , realice los siguientes pasos,
- Almacene las frecuencias del elemento de la array, es decir, la clave del mapa mp2 en variables, digamos freq1 y freq2 respectivamente.
- Almacene los conteos de frecuencias de freq1 y freq2 en variables digamos count1 y count2 .
- Compruebe si la diferencia entre freq2 y freq1 es igual a 1 y el valor de count2 es igual a 1 , luego actualice ans a max(ans, i+1) .
- De lo contrario, si la diferencia entre freq1 y freq2 es igual a 1 y el valor de count1 es igual a 1 , actualice ans a max(ans, i+1) .
- Finalmente, después de completar los pasos anteriores, imprima el valor de ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// length of the required prefix
int maxPrefixLen(int arr[], int N)
{
// Stores the frequency of
// elements
unordered_map<int, int> a, b;
// Stores the maximum length
// of the prefix satisfying
// the conditions
int ans = 1;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Stores the count of
// current element
int curr = a[arr[i]];
// If curr is not
// equal to 0
if (curr != 0) {
// Decrement b[curr]
// by 1
b[curr]--;
// If b[curr] is 0
if (b[curr] == 0) {
// Remove b[curr]
// from the b
b.erase(curr);
}
}
// Update
a[arr[i]]++;
b[curr + 1]++;
// If all elements in the
// prefix are same or if
// all elements have frequency
// 1
if (a[arr[i]] == i + 1
or (b.find(1) != b.end() and b[1] == i + 1)) {
// Update the value of ans
ans = max(ans, i + 1);
}
// Else if the size of b
// is 2
else if (b.size() == 2) {
auto p = b.begin();
auto q = p;
// Increment q by 1
q++;
int freq1 = p->first;
int freq2 = q->first;
int count1 = p->second;
int count2 = q->second;
// If difference between
// freq2 and freq1 is
// equal to 1 and if
// count2 is equal to 1
if (freq2 - freq1 == 1 and count2 == 1) {
// Update the value
// of ans
ans = max(ans, i + 1);
}
// If difference between
// freq1 and freq2 is
// equal to 1 and if
// count1 is equal to 1
else if (freq1 - freq2 == 1 and count1 == 1) {
// Update the value
// of ans
ans = max(ans, i + 1);
}
// If freq2 and count2 is 1
// or freq1 and count1 is 1
if ((freq2 == 1 and count2 == 1)
or (freq1 == 1 and count1 == 1)) {
// Update the value of
// ans
ans = max(ans, i + 1);
}
}
}
// Return ans
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxPrefixLen(arr, N);
}
Java
// Java program for the above approach
import java.util.HashMap;
class GFG {
// Function to find the maximum
// length of the required prefix
public static int maxPrefixLen(int arr[], int N)
{
// Stores the frequency of
// elements
HashMap<Integer, Integer> a = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> b = new HashMap<Integer, Integer>();
// Stores the maximum length
// of the prefix satisfying
// the conditions
int ans = 1;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Stores the count of
// current element
int curr = !a.containsKey(arr[i]) ? 0 : a.get(arr[i]);
// If curr is not
// equal to 0
if (curr != 0) {
// Decrement b[curr]
// by 1
b.put(curr, b.get(curr) - 1);
// If b[curr] is 0
if (b.get(curr) == 0)
{
// Remove b[curr]
// from the b
b.remove(curr);
}
}
// Update
if (a.containsKey(arr[i])) {
a.put(arr[i], a.get(arr[i]) + 1);
} else {
a.put(arr[i], 1);
}
if (b.containsKey(curr + 1)) {
b.put(curr + 1, b.get(curr + 1) + 1);
} else {
b.put(curr + 1, 1);
}
// If all elements in the
// prefix are same or if
// all elements have frequency
// 1
if (a.get(arr[i]) == i + 1 || (b.containsKey(1) && b.get(1) == i + 1))
{
// Update the value of ans
ans = Math.max(ans, i + 1);
}
else if (b.size() == 2) {
int p = b.keySet().toArray()[0].hashCode();
int q = b.keySet().toArray()[1].hashCode();
// Increment q by 1
int freq1 = p;
int freq2 = q;
int count1 = b.get(p);
int count2 = b.get(q);
// If difference between
// freq2 and freq1 is
// equal to 1 and if
// count2 is equal to 1
if ((freq2 - freq1) == 1 && count2 == 1)
{
// Update the value
// of ans
ans = Math.max(ans, i + 1);
}
// If difference between
// freq1 and freq2 is
// equal to 1 and if
// count1 is equal to 1
else if (freq1 - freq2 == 1 && count1 == 1)
{
// Update the value
// of ans
ans = Math.max(ans, i + 1);
}
// If freq2 and count2 is 1
// or freq1 and count1 is 1
if ((freq2 == 1 && count2 == 1) || (freq1 == 1 && count1 == 1))
{
// Update the value of
// ans
ans = Math.max(ans, i + 1);
}
}
}
// Return ans
return ans;
}
// Driver Code
public static void main(String args[]) {
int arr[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5 };
int N = arr.length;
System.out.println(maxPrefixLen(arr, N));
}
}
// This code is contributed by gfgking.
Python3
# Python3 program for the above approach
# Function to find the maximum
# length of the required prefix
def maxPrefixLen(arr, N):
# Stores the frequency of
# elements
a, b = {}, {}
# Stores the maximum length
# of the prefix satisfying
# the conditions
ans = 1
# Traverse the array arr[]
for i in range(N):
# Stores the count of
# current element
curr = 0 if (arr[i] not in a) else a[arr[i]]
# If curr is not
# equal to 0
if (curr != 0):
# Decrement b[curr]
# by 1
b[curr] -= 1
# If b[curr] is 0
if (b[curr] == 0):
# Remove b[curr]
# from the b
del b[curr]
# Update
a[arr[i]] = a.get(arr[i], 0) + 1
b[curr + 1] = b.get(curr + 1, 0) + 1
# If all elements in the
# prefix are same or if
# all elements have frequency
# 1
if (a[arr[i]] == i + 1 or
(1 in b) and b[1] == i + 1):
# Update the value of ans
ans = max(ans, i + 1)
# Else if the size of b
# is 2
elif (len(b) == 2):
p = list(b.keys())[0]
q = list(b.keys())[1]
freq1 = p
freq2 = q
count1 = b[p]
count2 = b[q]
# If difference between
# freq2 and freq1 is
# equal to 1 and if
# count2 is equal to 1
if (freq2 - freq1 == 1 and count2 == 1):
# Update the value
# of ans
ans = max(ans, i + 1)
# If difference between
# freq1 and freq2 is
# equal to 1 and if
# count1 is equal to 1
elif (freq1 - freq2 == 1 and count1 == 1):
# Update the value
# of ans
ans = max(ans, i + 1)
# If freq2 and count2 is 1
# or freq1 and count1 is 1
if ((freq2 == 1 and count2 == 1) or
(freq1 == 1 and count1 == 1)):
# Update the value of
# ans
ans = max(ans, i + 1)
# Return ans
return ans
# Driver Code
if __name__ == '__main__':
arr = [ 1, 1, 1, 2, 2, 2, 3,
3, 3, 4, 4, 4, 5 ]
N = len(arr)
print(maxPrefixLen(arr, N))
# This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum
// length of the required prefix
function maxPrefixLen(arr, N) {
// Stores the frequency of
// elements
let a = new Map();
let b = new Map();
// Stores the maximum length
// of the prefix satisfying
// the conditions
let ans = 1
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// Stores the count of
// current element
let curr = !(a.has(arr[i])) ? 0 : a.get(arr[i])
// If curr is not
// equal to 0
if (curr != 0) {
// Decrement b[curr]
// by 1
b.set(curr, b.get(curr) - 1)
// If b[curr] is 0
if (b.get(curr) == 0) {
// Remove b[curr]
// from the b
b.delete(curr)
}
}
// Update
if (a.has(arr[i])) {
a.set(arr[i], a.get(arr[i]) + 1)
} else {
a.set(arr[i], 1)
}
if (b.has(curr + 1)) {
b.set(curr + 1, b.get(curr + 1) + 1)
} else {
b.set(curr + 1, 1)
}
// If all elements in the
// prefix are same or if
// all elements have frequency
// 1
if (a.get(arr[i]) == i + 1 ||
(b.has(1)) && b.get(1) == i + 1) {
// Update the value of ans
ans = Math.max(ans, i + 1)
// Else if the size of b
// is 2
}
else if (b.size == 2) {
let p = [...b.keys()][0]
let q = [...b.keys()][1]
let freq1 = p
let freq2 = q
let count1 = b.get(p)
let count2 = b.get(q)
// If difference between
// freq2 and freq1 is
// equal to 1 and if
// count2 is equal to 1
if (freq2 - freq1 == 1 && count2 == 1) {
// Update the value
// of ans
ans = Math.max(ans, i + 1)
}
// If difference between
// freq1 and freq2 is
// equal to 1 and if
// count1 is equal to 1
else if (freq1 - freq2 == 1 && count1 == 1) {
// Update the value
// of ans
ans = Math.max(ans, i + 1)
}
// If freq2 and count2 is 1
// or freq1 and count1 is 1
if ((freq2 == 1 && count2 == 1) ||
(freq1 == 1 && count1 == 1)) {
// Update the value of
// ans
ans = Math.max(ans, i + 1)
}
}
}
// Return ans
return ans
}
// Driver Code
let arr = [1, 1, 1, 2, 2, 2, 3,
3, 3, 4, 4, 4, 5]
N = arr.length
document.write(maxPrefixLen(arr, N))
// This code is contributed by gfgking
</script>
Producción:
13
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aayushstar300 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA