Dada una string str , la tarea es verificar si la frecuencia de cualquier carácter es más de la mitad de la longitud de la string dada. Los caracteres pueden ser letras mayúsculas o minúsculas, dígitos y caracteres especiales.
Ejemplos:
Entrada: str = “AAa*2AAAA”
Salida: Sí
La frecuencia de ‘A’ es más de la mitad de la longitud de la string.Entrada: str = “abB@2a”
Salida: No
Enfoque: El problema se puede resolver fácilmente utilizando una array de frecuencias de longitud 2 8 , es decir, 256, ya que hay 256 caracteres diferentes. Iterar a través de la string y aumentar el recuento del carácter en uno en la array de frecuencia cada vez que se encuentre. Finalmente, itere a través de la array de frecuencias para verificar si la frecuencia de cualquier carácter es más de la mitad de la longitud de la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAXN 256
// Function that returns true if the frequency
// of any character is more than half the
// length of the string
bool checkHalfFrequency(string str)
{
// Length of the string
int L = str.size();
// Initialize a frequency array
int fre[MAXN] = { 0 };
// Iterate the string and update the
// frequency of each of the character
for (int i = 0; i < L; i++)
fre[str[i]]++;
// Iterate the frequency array
for (int i = 0; i < MAXN; i++)
// If condition is satisfied
if (fre[i] > L / 2)
return true;
return false;
}
// Driver code
int main()
{
string str = "GeeksforGeeks";
if (checkHalfFrequency(str))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAXN = 256;
// Function that returns true if the frequency
// of any character is more than half the
// length of the string
static boolean checkHalfFrequency(String str)
{
// Length of the string
int L = str.length();
// Initialize a frequency array
int fre[] = new int[MAXN];
// Iterate the string and update the
// frequency of each of the character
for (int i = 0; i < L; i++)
{
fre[str.charAt(i)]++;
}
// Iterate the frequency array
for (int i = 0; i < MAXN; i++) // If condition is satisfied
{
if (fre[i] > L / 2)
{
return true;
}
}
return false;
}
// Driver code
public static void main(String[] args)
{
String str = "GeeksforGeeks";
if (checkHalfFrequency(str))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach
MAXN = 256
# Function that returns true if the frequency
# of any character is more than half the
# length of the String
def checkHalfFrequency(Str):
# Length of the String
L = len(Str)
# Initialize a frequency array
fre = [0 for i in range(MAXN)]
# Iterate the and update the
# frequency of each of the character
for i in range(L):
fre[ord(Str[i])] += 1
# Iterate the frequency array
for i in range(MAXN):
# If condition is satisfied
if (fre[i] > L // 2):
return True
return False
# Driver code
Str = "GeeksforGeeks"
if (checkHalfFrequency(Str)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAXN = 256;
// Function that returns true if the frequency
// of any character is more than half the
// length of the string
static bool checkHalfFrequency(string str)
{
// Length of the string
int L = str.Length;
// Initialize a frequency array
int[] fre = new int[MAXN];
// Iterate the string and update the
// frequency of each of the character
for (int i = 0; i < L; i++)
{
fre[str[i]]++;
}
// Iterate the frequency array
for (int i = 0; i < MAXN; i++) // If condition is satisfied
{
if (fre[i] > L / 2)
{
return true;
}
}
return false;
}
// Driver code
public static void Main()
{
string str = "GeeksforGeeks";
if (checkHalfFrequency(str))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
/* This code contributed by Code_Mech */
PHP
<?php
// PHP implementation of the approach
// Function that returns true if the frequency
// of any character is more than half the
// length of the string
function checkHalfFrequency($str)
{
$MAXN = 256;
// Length of the string
$L = strlen($str);
// Initialize a frequency array
$fre = array_fill(0, $MAXN, 0 );
// Iterate the string and update the
// frequency of each of the character
for ($i = 0; $i < $L; $i++)
{
$fre[ord($str[$i])]++;
}
// Iterate the frequency array
for ($i = 0; $i < $MAXN; $i++) // If condition is satisfied
{
if ($fre[$i] > (int)($L / 2))
{
return true;
}
}
return false;
}
// Driver code
$str = "GeeksforGeeks";
if (checkHalfFrequency($str))
{
echo("Yes");
}
else
{
echo("No");
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation of the approach
var MAXN = 256
// Function that returns true if the frequency
// of any character is more than half the
// length of the string
function checkHalfFrequency(str)
{
// Length of the string
var L = str.length;
// Initialize a frequency array
var fre = Array(MAXN);
// Iterate the string and update the
// frequency of each of the character
for(var i = 0; i < L; i++)
fre[str[i]]++;
// Iterate the frequency array
for(var i = 0; i < MAXN; i++)
// If condition is satisfied
if (fre[i] > L / 2)
return true;
return false;
}
// Driver code
var str = "GeeksforGeeks";
if (checkHalfFrequency(str))
document.write( "Yes");
else
document.write( "No");
// This code is contributed by itsok
</script>
No
Complejidad de tiempo: O(N), N = longitud de la string
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA