Сделать все символы в заданной строке равными, заменив гласную на согласную и наоборот

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

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

Примеры:

Input: str = “banana”
Output: 3
Explanation: Convert all consonants to Vowel character A

Input: str = “hexon”
Output: 5
Explanation: Convert E to O first then all the consonants to Alphabet O

Подход: Основная загвоздка здесь в том, что:

  • Операции, необходимые для замены согласного на другой согласный или гласного на другой гласный: 2 Операция
  • Операция, необходимая для замены согласной на гласную или гласной на согласную: 1 Операция

Итак, ясно, что более экономично заменить согласную на гласную или гласную на согласную, чем заменить согласную на другую согласную или гласную на другую гласную.

Теперь, чтобы решить этот вопрос, выполните следующие действия:

  1. Подсчитайте частоту всех символов и найдите согласную и гласную с наибольшей частотой, скажем, А и В соответственно.
  2. Попробуйте изменить все символы на A и B и сохраните необходимые операции в переменных minA и minB соответственно.
  3. Минимум minA и minB является ответом на эту проблему.

Ниже приведена реализация описанного выше подхода.

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

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