Dada una array A[] de N strings de caracteres en minúsculas , la tarea es encontrar el número máximo de strings, de modo que un carácter tenga mayoría, es decir, la aparición de un carácter en todas las strings es mayor que todos los demás caracteres combinados.
Ejemplos:
Entrada: A[] = {“aba”, “abcde”, “aba”}
Salida: 2
Explicación: Al elegir {“aba”, “aba”}, la ocurrencia del carácter ‘a’ es 4 y la ocurrencia del resto de los caracteres es 2, que es menor que 4. Por lo tanto, se puede elegir un máximo de 2 strings.Entrada: A[] = {“bzc”, “zzzdz”, “e”}
Salida: 3
Explicación: Se pueden elegir todas las strings, donde ‘z’ tiene la mayoría.
Enfoque: hay una solución codiciosa para este problema. La idea es que, considere todos los caracteres en minúscula de la ‘a’ a la ‘z’ y para cada carácter, encuentre el número máximo de strings que se pueden elegir, de modo que la ocurrencia de ese carácter sea mayor que todos los demás caracteres combinados. El máximo de ellos será la respuesta. Ahora, el problema principal es cómo encontrar el número máximo de strings de modo que un carácter en particular tenga mayoría, para resolver esto, use un algoritmo codicioso . La idea es que, para encontrar el número máximo de strings para un carácter particular ‘ch’, intente elegir las strings en las que aparece ‘ch’es mayor en comparación con la aparición de todos los demás caracteres, es decir, las strings en las que (aparición de ‘ch’ – aparición de todos los demás caracteres) es máxima , por lo que será posible añadir más strings en el futuro.
Siga los pasos a continuación para resolver el problema:
- Defina una función CalDif(string s, char ch) y realice las siguientes tareas:
- Inicialice las variables chcount como 0 para almacenar el recuento de ese carácter y othercount como 0 para almacenar el recuento de otros caracteres.
- Recorra la string s usando la variable x y realice las siguientes tareas:
- Si el carácter en la posición actual es ch, aumente el valor de chcount en 1 ; de lo contrario, aumente el valor de othercount en 1.
- Devuelve la diferencia entre chcount y othercount.
- Inicialice la variable ans y asigne 0 , almacenará la respuesta final.
- Iterar sobre el rango de caracteres en minúsculas [a, z] usando la variable i y realizar los siguientes pasos:
- Inicialice un vector arr[] de longitud N , donde arr[i] almacenará (ocurrencia de ch – ocurrencia de todos los demás caracteres) para la i-ésima string.
- Ejecutar un bucle de i=0 a N-1
- Para la i -ésima string, calcule (ocurrencia de ch – ocurrencia de todos los demás caracteres) usando la función CalDiff(A[i], ch) y asígnela a arr[i] .
- Ordenar arr[] en orden decreciente.
- Inicialice dos variables temp y count y asígneles 0 .
- Atraviese la array arr[] y haga temp += arr[i] y count++ , donde i comienza desde 0 , hasta temp <= 0 .
- Establezca el valor de ans max de ans y cuente .
- Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.
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 calculate (occurrence of ch -
// occurrence of all other characters combined)
int CalDiff(string s, char ch)
{
// Initialize ch count as 0
int chcount = 0;
// Initialize all other char count as 0
int othercount = 0;
// Traversing the string
for (auto x : s) {
// Current character is ch
if (x == ch)
chcount++;
// Current character is not ch
else
othercount++;
}
// Return the final result
return (chcount - othercount);
}
// Function to calculate maximum number of string
// with one character as majority
int MaximumNumberOfString(string A[], int N)
{
// Initializing ans with 0, to store final answer
int ans = 0;
// For every character from 'a' to 'z' run loop
for (char ch = 'a'; ch <= 'z'; ch++) {
// Initialize arr to store character count
// difference
vector<int> arr(N);
// Traverse every string
for (int i = 0; i < N; i++) {
// Calculate the required value by
// function call and assign it to arr[i]
arr[i] = CalDiff(A[i], ch);
}
// Sort arr[] in decreasing order
sort(arr.begin(), arr.end(), greater<int>());
// Initialize temp and count as 0
int temp = 0, count = 0;
// Adding the first arr[] element to temp
temp += arr[0];
// Maintaining j as index
int j = 1;
// Run loop until temp <= 0
while (temp > 0) {
// Increasing count
count++;
// Adding temp with next arr[] element
if (j != N)
temp += arr[j++];
else
break;
}
// Set ans as max of ans and count
ans = max(ans, count);
}
// Returning the final result
return ans;
}
// Driver Code
int main()
{
// Input
string A[] = { "aba", "abcde", "aba" };
int N = sizeof(A) / sizeof(A[0]);
// Function call
cout << MaximumNumberOfString(A, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to calculate (occurrence of ch -
// occurrence of all other characters combined)
static int CalDiff(String s, char ch)
{
// Initialize ch count as 0
int chcount = 0;
// Initialize all other char count as 0
int othercount = 0;
// Traversing the String
for (int x : s.toCharArray())
{
// Current character is ch
if (x == ch)
chcount++;
// Current character is not ch
else
othercount++;
}
// Return the final result
return (chcount - othercount);
}
// Function to calculate maximum number of String
// with one character as majority
static int MaximumNumberOfString(String A[], int N)
{
// Initializing ans with 0, to store final answer
int ans = 0;
// For every character from 'a' to 'z' run loop
for (char ch = 'a'; ch <= 'z'; ch++) {
// Initialize arr to store character count
// difference
int []arr = new int[N];
// Traverse every String
for (int i = 0; i < N; i++) {
// Calculate the required value by
// function call and assign it to arr[i]
arr[i] = CalDiff(A[i], ch);
}
// Sort arr[] in decreasing order
Arrays.sort(arr);
arr = reverse(arr);
// Initialize temp and count as 0
int temp = 0, count = 0;
// Adding the first arr[] element to temp
temp += arr[0];
// Maintaining j as index
int j = 1;
// Run loop until temp <= 0
while (temp > 0)
{
// Increasing count
count++;
// Adding temp with next arr[] element
if (j != N)
temp += arr[j++];
else
break;
}
// Set ans as max of ans and count
ans = Math.max(ans, count);
}
// Returning the final result
return ans;
}
static int[] reverse(int a[]) {
int i, n = a.length, t;
for (i = 0; i < n / 2; i++) {
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void main(String[] args)
{
// Input
String A[] = { "aba", "abcde", "aba" };
int N = A.length;
// Function call
System.out.print(MaximumNumberOfString(A, N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python 3 program for the above approach # Function to calculate (occurrence of ch - # occurrence of all other characters combined) def CalDiff(s, ch): # Initialize ch count as 0 chcount = 0 # Initialize all other char count as 0 othercount = 0 # Traversing the string for x in s: # Current character is ch if (x == ch): chcount += 1 # Current character is not ch else: othercount += 1 # Return the final result return (chcount - othercount) # Function to calculate maximum number of string # with one character as majority def MaximumNumberOfString(A, N): # Initializing ans with 0, to store final answer ans = 0 # For every character from 'a' to 'z' run loop for ch in range(97,123,1): # Initialize arr to store character count # difference arr = [0 for i in range(N)] # Traverse every string for i in range(N): # Calculate the required value by # function call and assign it to arr[i] arr[i] = CalDiff(A[i], chr(ch)) # Sort arr[] in decreasing order arr.sort(reverse = True) # Initialize temp and count as 0 temp = 0 count = 0 # Adding the first arr[] element to temp temp += arr[0] # Maintaining j as index j = 1 # Run loop until temp <= 0 while (temp > 0): # Increasing count count += 1 # Adding temp with next arr[] element if (j != N): temp += arr[j] j += 1 else: break # Set ans as max of ans and count ans = max(ans, count) # Returning the final result return ans # Driver Code if __name__ == '__main__': # Input A = ["aba", "abcde", "aba"] N = len(A) # Function call print(MaximumNumberOfString(A, N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate (occurrence of ch -
// occurrence of all other characters combined)
static int CalDiff(string s, char ch)
{
// Initialize ch count as 0
int chcount = 0;
// Initialize all other char count as 0
int othercount = 0;
// Traversing the String
foreach(int x in s.ToCharArray())
{
// Current character is ch
if (x == ch)
chcount++;
// Current character is not ch
else
othercount++;
}
// Return the final result
return(chcount - othercount);
}
// Function to calculate maximum number of String
// with one character as majority
static int MaximumNumberOfString(string[] A, int N)
{
// Initializing ans with 0, to store final answer
int ans = 0;
// For every character from 'a' to 'z' run loop
for(char ch = 'a'; ch <= 'z'; ch++)
{
// Initialize arr to store character count
// difference
int []arr = new int[N];
// Traverse every String
for(int i = 0; i < N; i++)
{
// Calculate the required value by
// function call and assign it to arr[i]
arr[i] = CalDiff(A[i], ch);
}
// Sort arr[] in decreasing order
Array.Sort(arr);
arr = reverse(arr);
// Initialize temp and count as 0
int temp = 0, count = 0;
// Adding the first arr[] element to temp
temp += arr[0];
// Maintaining j as index
int j = 1;
// Run loop until temp <= 0
while (temp > 0)
{
// Increasing count
count++;
// Adding temp with next arr[] element
if (j != N)
temp += arr[j++];
else
break;
}
// Set ans as max of ans and count
ans = Math.Max(ans, count);
}
// Returning the final result
return ans;
}
static int[] reverse(int[] a)
{
int i, n = a.Length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Driver Code
public static void Main(String []args)
{
// Input
string[] A = { "aba", "abcde", "aba" };
int N = A.Length;
// Function call
Console.WriteLine(MaximumNumberOfString(A, N));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Function to calculate (occurrence of ch -
// occurrence of all other characters combined)
function CalDiff(s, ch) {
// Initialize ch count as 0
let chcount = 0;
// Initialize all other char count as 0
let othercount = 0;
// Traversing the string
for (let x of s) {
// Current character is ch
if (x == ch) chcount++;
// Current character is not ch
else othercount++;
}
// Return the final result
return chcount - othercount;
}
// Function to calculate maximum number of string
// with one character as majority
function MaximumNumberOfString(A, N) {
// Initializing ans with 0, to store final answer
let ans = 0;
// For every character from 'a' to 'z' run loop
for (let ch = "a".charCodeAt(0); ch <= "z".charCodeAt(0); ch++) {
// Initialize arr to store character count
// difference
let arr = new Array(N);
// Traverse every string
for (let i = 0; i < N; i++) {
// Calculate the required value by
// function call and assign it to arr[i]
arr[i] = CalDiff(A[i], String.fromCharCode(ch));
}
// Sort arr[] in decreasing order
arr.sort((a, b) => b - a);
// Initialize temp and count as 0
let temp = 0,
count = 0;
// Adding the first arr[] element to temp
temp += arr[0];
// Maintaining j as index
let j = 1;
// Run loop until temp <= 0
while (temp > 0) {
// Increasing count
count++;
// Adding temp with next arr[] element
if (j != N) temp += arr[j++];
else break;
}
// Set ans as max of ans and count
ans = Math.max(ans, count);
}
// Returning the final result
return ans;
}
// Driver Code
// Input
let A = ["aba", "abcde", "aba"];
let N = A.length;
// Function call
document.write(MaximumNumberOfString(A, N));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
2
Complejidad de tiempo: O(N * |s|), donde |s| es la longitud máxima de la string.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ganapati_biswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA