Максимально встречающийся лексикографически наименьший символ в строке

Опубликовано: 27 Февраля, 2023

Дана строка, содержащая символы нижнего регистра. Задача состоит в том, чтобы напечатать максимальное количество символов во входной строке. Если 2 или более символов встречаются одинаковое количество раз, выведите лексикографически (по алфавиту) самый младший (первый) символ.

Примеры:

Input: test sample 
Output: e 
Explanation: e’t’, ‘e’ and ‘s’ appears 2 times, but ‘e’ is the lexicographically smallest character. 

Input: sample program
Output: a

В предыдущей статье, если максимальное количество раз встречается более одного символа, то возвращается любой из символов. В этом посте возвращается лексикографически наименьший символ из всех символов.
Подход: объявить массив freq[26] , который используется в качестве хэш-таблицы для хранения частот каждого символа во входной строке. Повторите строку и увеличьте количество freq[s[i]] для каждого символа. Перемещайтесь по массиву freq[] слева направо и отслеживайте символ, имеющий на данный момент максимальную частоту. Значение freq[i] представляет частоту символа (i + 'a').

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

Анализ сложности:

  • Временная сложность: O(n), где n — длина заданной входной строки.
  • Вспомогательное пространство: O(1).

Источник: Опыт интервью Сэйбер | Набор 2

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