Compruebe si la frecuencia de todos los caracteres puede volverse la misma con una sola eliminación

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *