Рубрики

Проверьте, может ли частота всех символов становиться одинаковой при одном удалении

Для данной строки, которая содержит буквы младшего алфавита, нам нужно удалить не более одного символа из этой строки таким образом, чтобы частота каждого отдельного символа в строке становилась одинаковой.

Примеры:

Input: str = “xyyz”
Output: Yes
We can remove character ’y’ from above
string to make the frequency of each
character same.

Input: str = “xyyzz”
Output: Yes
We can remove character ‘x’ from above
string to make the frequency of each
character same.

Input: str = “xxxxyyzz”
Output: No
It is not possible to make frequency of
each character same just by removing at
most one character from above string.

Подход : проблема может быть решена с использованием концепции хеширования . Главное, что нужно заметить в этой задаче, это то, что положение символов здесь не имеет значения, поэтому мы будем считать частоту символов, если все они одинаковы, то мы закончили и нет необходимости удалять какой-либо символ, чтобы сделать частоту одинаковых символов. В противном случае мы можем перебирать все символы один за другим и уменьшать их частоту на единицу, если все частоты становятся одинаковыми, тогда мы будем отмечать, что можно сделать частоту символов одинаковой не более чем на одно удаление, и если частоты не совпадают затем мы снова увеличим эту частоту и сделаем цикл для других символов.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для получения символа с той же частотой
// строка путем удаления не более одного символа
#include <bits/stdc++.h>

using namespace std;

#define M 26

  
// Служебный метод для получения индекса символа ch
// в нижних алфавитных символах

int getIdx(char ch)

{

    return (ch - 'a');

}

  
// Возвращает true, если все ненулевые элементы
// значения одинаковы

bool allSame(int freq[], int N)

{

    int same;

  

    // получаем первый ненулевой элемент

    int i;

    for (i = 0; i < N; i++) {

        if (freq[i] > 0) {

            same = freq[i];

            break;

        }

    }

  

    // проверяем равенство каждого элемента с переменной

    for (int j = i + 1; j < N; j++)

        if (freq[j] > 0 && freq[j] != same)

            return false;

  

    return true;

}

  
// Возвращает true, если мы можем сделать все символы
// частоты одинаковые

bool possibleSameCharFreqByOneRemoval(string str)

{

    int l = str.length();

  

    // заполняем частотный массив

    int freq[M] = { 0 };

    for (int i = 0; i < l; i++)

        freq[getIdx(str[i])]++;

  

    // если все частоты одинаковы, возвращаем true

    if (allSame(freq, M))

        return true;

  

    / * Попробуйте уменьшить частоту всех символов

        один, а затем проверить все равенство всех

        ненулевые частоты * /

    for (char c = 'a'; c <= 'z'; c++) {

        int i = getIdx(c);

  

        // Проверяем символ только если он встречается в str

        if (freq[i] > 0) {

            freq[i]--;

  

            if (allSame(freq, M))

                return true;

            freq[i]++;

        }

    }

  

    return false;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    string str = "xyyzz";

    if (possibleSameCharFreqByOneRemoval(str))

        cout << "Yes";

    else

        cout << "No";

}

Джава

// Java-программа для получения символа с той же частотой
// строка путем удаления не более одного символа

public class GFG {

  

    static final int M = 26;

  

    // Служебный метод для получения индекса символа ch

    // в нижних алфавитных символах

    static int getIdx(char ch)

    {

        return (ch - 'a');

    }

  

    // Возвращает true, если все ненулевые элементы

    // значения одинаковы

    static boolean allSame(int freq[], int N)

    {

        int same = 0;

  

        // получаем первый ненулевой элемент

        int i;

        for (i = 0; i < N; i++) {

            if (freq[i] > 0) {

                same = freq[i];

                break;

            }

        }

  

        // проверяем равенство каждого элемента с

        // переменная такая же

        for (int j = i + 1; j < N; j++)

            if (freq[j] > 0 && freq[j] != same)

                return false;

  

        return true;

    }

  

    // Возвращает true, если мы можем сделать все символы

    // частоты одинаковые

    static boolean possibleSameCharFreqByOneRemoval(String str)

    {

        int l = str.length();

  

        // заполняем частотный массив

        int[] freq = new int[M];

  

        for (int i = 0; i < l; i++)

            freq[getIdx(str.charAt(i))]++;

  

        // если все частоты одинаковы, возвращаем true

        if (allSame(freq, M))

            return true;

  

        / * Попробуйте уменьшить частоту всех символов

            один, а затем проверить все равенство всех

            ненулевые частоты * /

        for (char c = 'a'; c <= 'z'; c++) {

            int i = getIdx(c);

  

            // Проверяем символ только если он встречается в str

            if (freq[i] > 0) {

                freq[i]--;

  

                if (allSame(freq, M))

                    return true;

                freq[i]++;

            }

        }

  

        return false;

    }

  

    // Код драйвера для тестирования вышеуказанных методов

    public static void main(String args[])

    {

        String str = "xyyzz";

        if (possibleSameCharFreqByOneRemoval(str))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}
// Этот код предоставлен Sumit Ghosh

Python 3

# Python3 программа для получения символа с той же частотой
# строка при удалении не более одного символа

M = 26

  
# Служебный метод для получения индекса символа ch
# в нижнем алфавите

def getIdx(ch):

    return (ord(ch) - ord('a'))

  
# Возвращает true, если все ненулевые элементы
# значения одинаковы

def allSame(freq, N):

      

    # получить первый ненулевой элемент

    for i in range(0, N):

        if(freq[i] > 0):

            same = freq[i]

            break

          

    # проверить равенство каждого элемента

    # с той же переменной

    for j in range(i + 1, N):

        if(freq[j] > 0 and freq[j] != same):

            return False

  

    return True

  
# Возвращает true, если мы можем сделать все
# символьные частоты одинаковы

def possibleSameCharFreqByOneRemoval(str1):

    l = len(str1)

  

    # заполнить массив частот

    freq = [0] * M

    for i in range(0, l):

        freq[getIdx(str1[i])] += 1

          

    # если все частоты одинаковы,

    # затем верните true

    if(allSame(freq, M)):

        return True

      

    # Попробуйте уменьшить частоту всех символов

    # по одному, а затем проверить все равенство всех

    # ненулевые частоты

    for i in range(0, 26):

          

        # Проверять символ только если он

        # встречается в стр

        if(freq[i] > 0):

            freq[i] -= 1

  

            if(allSame(freq, M)):

                return True

            freq[i] += 1

  

    return False

  
# Код драйвера

if __name__ == "__main__":

    str1 = "xyyzz"

    if(possibleSameCharFreqByOneRemoval(str1)):

        print("Yes")

    else:

        print("No")

  
# Этот код предоставлен Sairahul099

C #

// C # программа для получения той же частоты
// символьная строка путем удаления
// максимум один символ

using System;

  

class GFG {

    static int M = 26;

  

    // Служебный метод для получения

    // индекс символа ch

    // в нижних алфавитных символах

    static int getIdx(char ch)

    {

        return (ch - 'a');

    }

  

    // Возвращает true, если все

    // ненулевые элементы

    // значения одинаковы

    static bool allSame(int[] freq,

                        int N)

    {

        int same = 0;

  

        // получаем первый ненулевой элемент

        int i;

        for (i = 0; i < N; i++) {

            if (freq[i] > 0) {

                same = freq[i];

                break;

            }

        }

  

        // проверяем равенство

        // каждый элемент с

        // переменная такая же

        for (int j = i + 1; j < N; j++)

            if (freq[j] > 0 && freq[j] != same)

                return false;

  

        return true;

    }

  

    // Возвращает true, если мы

    // можем сделать весь символ

    // частоты одинаковые

    static bool possibleSameCharFreqByOneRemoval(string str)

    {

        int l = str.Length;

  

        // заполняем частотный массив

        int[] freq = new int[M];

  

        for (int i = 0; i < l; i++)

            freq[getIdx(str[i])]++;

  

        // если все частоты одинаковы,

        // затем возвращаем true

        if (allSame(freq, M))

            return true;

  

        / * Попробуйте уменьшить частоту всех

            символ за одним, а затем проверить

            все равенство всех ненулевых

            частоты * /

        for (char c = 'a'; c <= 'z'; c++) {

            int i = getIdx(c);

  

            // Проверяем символ только если

            // это происходит в str

            if (freq[i] > 0) {

                freq[i]--;

  

                if (allSame(freq, M))

                    return true;

                freq[i]++;

            }

        }

  

        return false;

    }

  

    // Код драйвера

    public static void Main()

    {

        string str = "xyyzz";

        if (possibleSameCharFreqByOneRemoval(str))

            Console.Write("Yes");

        else

            Console.Write("No");

    }

}

  
// Этот код добавлен
// ChitraNayal

PHP

<?php 
// PHP программа для получения той же частоты
// символьная строка путем удаления at
// самый один символ

$M = 26;

  
// Служебный метод для получения индекса
// символа ch в нижнем
// символы алфавита

function getIdx($ch)

{

    return ($ch - 'a');

}

  
// Возвращает true, если все
// ненулевые элементы
// значения одинаковы

function allSame(&$freq, $N)

{

    // получаем первый ненулевой элемент

    for ($i = 0; $i < $N; $i++)

    {

        if ($freq[$i] > 0)

        {

            $same = $freq[$i];

            break;

        }

    }

  

    // проверяем равенство каждого

    // элемент с такой же переменной

    for ($j = $i + 1; $j < $N; $j++)

        if ($freq[$j] > 0 && 

            $freq[$j] != $same)

            return false;

  

    return true;

}

  
// Возвращает true, если мы
// можем сделать весь символ
// частоты одинаковые

function possibleSameCharFreqByOneRemoval($str)

{

    global $M;

    $l = strlen($str);

  

    // заполняем частотный массив

    $freq = array_fill(0, $M, NULL);

    for ($i = 0; $i < $l; $i++)

        $freq[getIdx($str[$i])]++;

  

    // если все частоты одинаковы,

    // затем возвращаем true

    if (allSame($freq, $M))

        return true;

  

    / * Попробуйте уменьшить частоту всех

        символ за одним, а затем проверить

        все равенство всех ненулевых

        частоты * /

    for ($c = 'a'; $c <= 'z'; $c++)

    {

        $i = getIdx($c);

  

        // Проверяем только символ

        // если это происходит в str

        if ($freq[$i] > 0)

        {

            $freq[$i]--;

  

            if (allSame($freq, $M))

                return true;

            $freq[$i]++;

        }

    }

  

    return false;

}

  
// Код драйвера

$str = "xyyzz";

if (possibleSameCharFreqByOneRemoval($str))

echo "Yes";

else

echo "No";

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Yes

Сложность времени: O (n) при условии, что размер алфавита постоянен.

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проверьте, может ли частота всех символов становиться одинаковой при одном удалении

0.00 (0%) 0 votes