Минимизируйте изменения, чтобы сделать все символы равными, заменив гласную на согласную и наоборот.

Опубликовано: 21 Сентября, 2022

Для заданной строки str[] символов нижнего регистра задача состоит в том, чтобы сделать все символы строки равными за минимальное количество операций так, чтобы в каждой операции либо выбирался гласный звук и заменялся на согласный, либо наоборот.

Примеры:

Input: str[] = “geeksforgeeks”
Output: 10
Explanation: To make all the characters equal, make the following changes – 

  1. Change ‘o’ to a consonant(let’s say) ‘z’ and then to ‘e’
  2. Change every other consonant(‘g’, ‘k’, ‘s’, ‘ f’, ‘r’, ) to ‘e’

This results in the string str = “eeeeeeeeeeeee” and the total number of operations performed is 10.

Input: str[] = “coding”
Output: 6

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

  • Cv = стоимость замены всех символов на максимально встречающуюся гласную = нет. согласных + (общее количество гласных – частота максимальной встречаемости гласных) * 2
  • Копия = стоимость замены всех символов на максимально встречающийся согласный = нет. гласных + (общее количество согласных – частота максимальной встречаемости согласного) * 2

Теперь минимум из этих двух, т. е. min(Cv, Cc) , даст необходимое минимальное количество шагов, за которые мы можем преобразовать строку. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную ans, vowels и consonants как 0 , чтобы сохранить ответ, количество гласных и количество согласных.
  • Инициализируйте 2 переменные max_vowels и max_consonants как INT_MIN , чтобы найти максимальное количество встречающихся гласных и максимальное количество согласных в данной строке.
  • Инициализируйте 2 unordered_map<char, int> freq_vowels[] и freq_consonant[] для хранения частоты гласных и согласных.
  • Переберите диапазон [0, N), используя переменную i , и выполните следующие шаги:
    • Если текущий символ является гласным, то увеличьте количество гласных на 1 и его частоту в карте на 1 , в противном случае сделайте это для согласного.
  • Пройдите обе unordered_maps и найдите максимальное количество встречающихся гласных и согласных.
  • Используя приведенную выше формулу, вычислите ответ.
  • После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ