Для данной строки, которая содержит буквы младшего алфавита, нам нужно удалить не более одного символа из этой строки таким образом, чтобы частота каждого отдельного символа в строке становилась одинаковой.
Примеры:
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 ++
#include <bits/stdc++.h>
using namespace std;
#define M 26
int getIdx(char ch)
{
return (ch - 'a');
}
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;
}
bool possibleSameCharFreqByOneRemoval(string str)
{
int l = str.length();
int freq[M] = { 0 };
for (int i = 0; i < l; i++)
freq[getIdx(str[i])]++;
if (allSame(freq, M))
return true;
for (char c = 'a'; c <= 'z'; c++) {
int i = getIdx(c);
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";
}
|
Джава
public class GFG {
static final int M = 26;
static int getIdx(char ch)
{
return (ch - 'a');
}
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;
}
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))]++;
if (allSame(freq, M))
return true;
for (char c = 'a'; c <= 'z'; c++) {
int i = getIdx(c);
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");
}
}
|
Python 3
M = 26
def getIdx(ch):
return (ord(ch) - ord('a'))
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
def possibleSameCharFreqByOneRemoval(str1):
l = len(str1)
freq = [0] * M
for i in range(0, l):
freq[getIdx(str1[i])] += 1
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")
|
C #
using System;
class GFG {
static int M = 26;
static int getIdx(char ch)
{
return (ch - 'a');
}
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;
}
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])]++;
if (allSame(freq, M))
return true;
for (char c = 'a'; c <= 'z'; c++) {
int i = getIdx(c);
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");
}
}
|
PHP
<?php
$M = 26;
function getIdx($ch)
{
return ($ch - 'a');
}
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;
}
function possibleSameCharFreqByOneRemoval($str)
{
global $M;
$l = strlen($str);
$freq = array_fill(0, $M, NULL);
for ($i = 0; $i < $l; $i++)
$freq[getIdx($str[$i])]++;
if (allSame($freq, $M))
return true;
for ($c = 'a'; $c <= 'z'; $c++)
{
$i = getIdx($c);
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";
?>
|
Выход:
Yes
Сложность времени: O (n) при условии, что размер алфавита постоянен.
Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
- Программа для проверки четности всех символов
- Проверьте, есть ли в строке все символы с одинаковой частотой, допускается одно изменение
- Проверьте, составляет ли частота символов в строке последовательность Фибоначчи
- Максимальная длина сбалансированной строки после замены и удаления символов
- Удалить четные символы из строки
- Печать символов в порядке убывания частоты
- Строка с частотой символов в Lucas Sequence
- Минимальные операции, чтобы сделать частоту всех символов равной K
- Символ, частота которого равна сумме частот других символов данной строки
- Количество позиций для разбиения строки таким образом, чтобы в каждой подстроке присутствовало не менее m символов с одинаковой частотой
- Проверьте, является ли частота символа в одной строке фактором или кратна частоте того же символа в другой строке
- Проверьте, одинакова ли частота всех цифр в числе
- Проверьте, является ли частота любого символа больше половины длины строки
- Проверьте, содержат ли две строки одинаковые символы в одинаковом порядке
- Проверьте, имеют ли обе половины строки одинаковый набор символов
Проверьте, может ли частота всех символов становиться одинаковой при одном удалении
0.00 (0%) 0 votes