Dada una string que contiene caracteres alfabéticos inferiores, debemos eliminar como máximo un carácter de esta string de tal manera que la frecuencia de cada carácter distinto sea la misma en la string.
Ejemplos:
C++
// C++ program to get same frequency character
// string by removal of at most one char
#include <bits/stdc++.h>
using namespace std;
#define M 26
// Utility method to get index of character ch
// in lower alphabet characters
int getIdx(char ch)
{
return (ch - 'a');
}
// Returns true if all non-zero elements
// values are same
bool allSame(int freq[], int N)
{
int same;
// get first non-zero element
int i;
for (i = 0; i < N; i++) {
if (freq[i] > 0) {
same = freq[i];
break;
}
}
// check equality of each element with variable same
for (int j = i + 1; j < N; j++)
if (freq[j] > 0 && freq[j] != same)
return false;
return true;
}
// Returns true if we can make all character
// frequencies same
bool possibleSameCharFreqByOneRemoval(string str)
{
int l = str.length();
// fill frequency array
int freq[M] = { 0 };
for (int i = 0; i < l; i++)
freq[getIdx(str[i])]++;
// if all frequencies are same, then return true
if (allSame(freq, M))
return true;
/* Try decreasing frequency of all character
by one and then check all equality of all
non-zero frequencies */
for (char c = 'a'; c <= 'z'; c++) {
int i = getIdx(c);
// Check character only if it occurs in str
if (freq[i] > 0) {
freq[i]--;
if (allSame(freq, M))
return true;
freq[i]++;
}
}
return false;
}
// Driver code to test above methods
int main()
{
string str = "xyyzz";
if (possibleSameCharFreqByOneRemoval(str))
cout << "Yes";
else
cout << "No";
}
Java
// Java program to get same frequency character
// string by removal of at most one char
public class GFG {
static final int M = 26;
// Utility method to get index of character ch
// in lower alphabet characters
static int getIdx(char ch)
{
return (ch - 'a');
}
// Returns true if all non-zero elements
// values are same
static boolean allSame(int freq[], int N)
{
int same = 0;
// get first non-zero element
int i;
for (i = 0; i < N; i++) {
if (freq[i] > 0) {
same = freq[i];
break;
}
}
// check equality of each element with
// variable same
for (int j = i + 1; j < N; j++)
if (freq[j] > 0 && freq[j] != same)
return false;
return true;
}
// Returns true if we can make all character
// frequencies same
static boolean possibleSameCharFreqByOneRemoval(String str)
{
int l = str.length();
// fill frequency array
int[] freq = new int[M];
for (int i = 0; i < l; i++)
freq[getIdx(str.charAt(i))]++;
// if all frequencies are same, then return true
if (allSame(freq, M))
return true;
/* Try decreasing frequency of all character
by one and then check all equality of all
non-zero frequencies */
for (char c = 'a'; c <= 'z'; c++) {
int i = getIdx(c);
// Check character only if it occurs in str
if (freq[i] > 0) {
freq[i]--;
if (allSame(freq, M))
return true;
freq[i]++;
}
}
return false;
}
// Driver code to test above methods
public static void main(String args[])
{
String str = "xyyzz";
if (possibleSameCharFreqByOneRemoval(str))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to get same frequency character
# string by removal of at most one char
M = 26
# Utility method to get index of character ch
# in lower alphabet characters
def getIdx(ch):
return (ord(ch) - ord('a'))
# Returns true if all non-zero elements
# values are same
def allSame(freq, N):
# get first non-zero element
for i in range(0, N):
if(freq[i] > 0):
same = freq[i]
break
# check equality of each element
# with variable same
for j in range(i + 1, N):
if(freq[j] > 0 and freq[j] != same):
return False
return True
# Returns true if we can make all
# character frequencies same
def possibleSameCharFreqByOneRemoval(str1):
l = len(str1)
# fill frequency array
freq = [0] * M
for i in range(0, l):
freq[getIdx(str1[i])] += 1
# if all frequencies are same,
# then return true
if(allSame(freq, M)):
return True
# Try decreasing frequency of all character
# by one and then check all equality of all
# non-zero frequencies
for i in range(0, 26):
# Check character only if it
# occurs in str
if(freq[i] > 0):
freq[i] -= 1
if(allSame(freq, M)):
return True
freq[i] += 1
return False
# Driver code
if __name__ == "__main__":
str1 = "xyyzz"
if(possibleSameCharFreqByOneRemoval(str1)):
print("Yes")
else:
print("No")
# This code is contributed by Sairahul099
C#
// C# program to get same frequency
// character string by removal of
// at most one char
using System;
class GFG {
static int M = 26;
// Utility method to get
// index of character ch
// in lower alphabet characters
static int getIdx(char ch)
{
return (ch - 'a');
}
// Returns true if all
// non-zero elements
// values are same
static bool allSame(int[] freq,
int N)
{
int same = 0;
// get first non-zero element
int i;
for (i = 0; i < N; i++) {
if (freq[i] > 0) {
same = freq[i];
break;
}
}
// check equality of
// each element with
// variable same
for (int j = i + 1; j < N; j++)
if (freq[j] > 0 && freq[j] != same)
return false;
return true;
}
// Returns true if we
// can make all character
// frequencies same
static bool possibleSameCharFreqByOneRemoval(string str)
{
int l = str.Length;
// fill frequency array
int[] freq = new int[M];
for (int i = 0; i < l; i++)
freq[getIdx(str[i])]++;
// if all frequencies are same,
// then return true
if (allSame(freq, M))
return true;
/* Try decreasing frequency of all
character by one and then check
all equality of all non-zero
frequencies */
for (char c = 'a'; c <= 'z'; c++) {
int i = getIdx(c);
// Check character only if
// it occurs in str
if (freq[i] > 0) {
freq[i]--;
if (allSame(freq, M))
return true;
freq[i]++;
}
}
return false;
}
// Driver code
public static void Main()
{
string str = "xyyzz";
if (possibleSameCharFreqByOneRemoval(str))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to get same frequency
// character string by removal of at
// most one char
$M = 26;
// Utility method to get index
// of character ch in lower
// alphabet characters
function getIdx($ch)
{
return ($ch - 'a');
}
// Returns true if all
// non-zero elements
// values are same
function allSame(&$freq, $N)
{
// get first non-zero element
for ($i = 0; $i < $N; $i++)
{
if ($freq[$i] > 0)
{
$same = $freq[$i];
break;
}
}
// check equality of each
// element with variable same
for ($j = $i + 1; $j < $N; $j++)
if ($freq[$j] > 0 &&
$freq[$j] != $same)
return false;
return true;
}
// Returns true if we
// can make all character
// frequencies same
function possibleSameCharFreqByOneRemoval($str)
{
global $M;
$l = strlen($str);
// fill frequency array
$freq = array_fill(0, $M, NULL);
for ($i = 0; $i < $l; $i++)
$freq[getIdx($str[$i])]++;
// if all frequencies are same,
// then return true
if (allSame($freq, $M))
return true;
/* Try decreasing frequency of all
character by one and then check
all equality of all non-zero
frequencies */
for ($c = 'a'; $c <= 'z'; $c++)
{
$i = getIdx($c);
// Check character only
// if it occurs in str
if ($freq[$i] > 0)
{
$freq[$i]--;
if (allSame($freq, $M))
return true;
$freq[$i]++;
}
}
return false;
}
// Driver code
$str = "xyyzz";
if (possibleSameCharFreqByOneRemoval($str))
echo "Yes";
else
echo "No";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to get same
// frequency character string by
// removal of at most one char
let M = 26;
// Utility method to get index of character
// ch in lower alphabet characters
function getIdx(ch)
{
return (ch - 'a');
}
// Returns true if all non-zero elements
// values are same
function allSame(freq, N)
{
let same = 0;
// Get first non-zero element
let i;
for(i = 0; i < N; i++)
{
if (freq[i] > 0)
{
same = freq[i];
break;
}
}
// Check equality of each element with
// variable same
for(let j = i + 1; j < N; j++)
if (freq[j] > 0 && freq[j] != same)
return false;
return true;
}
// Returns true if we can make all character
// frequencies same
function possibleSameCharFreqByOneRemoval(str)
{
let l = str.length;
// Fill frequency array
let freq = new Array(M);
for(let i = 0; i < M; i++)
{
freq[i] = 0;
}
for(let i = 0; i < l; i++)
freq[getIdx(str[i])]++;
// If all frequencies are same,
// then return true
if (allSame(freq, M))
return true;
// Try decreasing frequency of all character
// by one and then check all equality of all
// non-zero frequencies
for(let c = 'a'; c <= 'z'; c++)
{
let i = getIdx(c);
// Check character only if
// it occurs in str
if (freq[i] > 0)
{
freq[i]--;
if (allSame(freq, M))
return true;
freq[i]++;
}
}
return false;
}
// Driver code
let str = "xyyzz";
if (possibleSameCharFreqByOneRemoval(str))
document.write("Yes");
else
document.write("No");
// This code is contributed by avanitrachhadiya2155
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA