Минимизируйте изменения, чтобы сделать все символы равными, заменив гласную на согласную и наоборот.
Для заданной строки str[] символов нижнего регистра задача состоит в том, чтобы сделать все символы строки равными за минимальное количество операций так, чтобы в каждой операции либо выбирался гласный звук и заменялся на согласный, либо наоборот.
Примеры:
Input: str[] = “geeksforgeeks”
Output: 10
Explanation: To make all the characters equal, make the following changes –
- Change ‘o’ to a consonant(let’s say) ‘z’ and then to ‘e’
- 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)