Повторить последнее вхождение каждого буквенно-цифрового символа в его позицию во времени семейства символов

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

Учитывая строку str[] размера N , задача состоит в том, чтобы закодировать ее таким образом, чтобы последнее вхождение каждого символа происходило до тех пор, пока его позиция в его семействе. Поскольку «а» является первым символом своего семейства (строчный алфавит), он останется «а», но «b» станет «bb», «D» станет «DDDD» и так далее. В случае числовых символов символ встречается столько раз, сколько его значение. Поскольку «1» остается «1», «2» становится «22», «0» становится «» и так далее. Но кроме последнего вхождения символа, остальные должны оставаться такими, какие они есть. Символы, отличные от (az), (AZ) и (0-9), остаются незатронутыми таким кодированием.

Примеры:

Input: str = “3bC”
Output: 333bbCCC
Explanation: In the given string, no character is repeated, hence all characters have one occurrence which is obviously their last. So every character will be encoded. As ‘3’ is a numeric character having the value 3 so it will occur thrice in the resultant string. ‘b’ is the second character of its family, so it will occur twice. And ‘C’ is the third capital character, hence it will occur three times.

Input: str = “Ea2, 0, E”
Output: Ea22,, EEEEE
Explanation: ‘E’ at the beginning isn’t its last occurrence in the string, thus it will remain as it is in the resultant string. While ‘a’ and ‘2’ are their only and last occurrences in the string, they will be changed to ‘a’ and ’22’ respectively. The characters ‘, ‘ and ‘ ‘ will remain unaffected. And ‘0’ will also be changed to ”.

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

  • Инициализируйте переменную string res как пустую строку для сохранения результата.
  • Инициализируйте массивы small и capital размером 26 и num размером 10 с 0 , чтобы сохранить последнее вхождение любого символа в строку str[].
  • Перебрать диапазон [0, N], используя переменную i и выполнив следующие задачи:
    • Если str[i] больше, чем равен '0' и меньше, чем равен '9' , тогда установите значение num[str[i] – '0'] как i.
    • Иначе Если str[i] больше, чем равно 'a' и меньше, чем равно 'z' , тогда установите значение small[str[i] – 'a'] как i.
    • Иначе Если str[i] больше, чем равно 'A' и меньше, чем равно 'Z' , тогда установите значение capital[str[i] – 'A'] как i.
  • Перебрать диапазон [0, N], используя переменную i и выполнив следующие задачи:
    • Если str[i] больше, чем равен '0' и меньше, чем равен '9', а num[str[i]-'0'] равен i , тогда инициализируйте переменную как str [i]-' 0' и добавьте str[i] в результирующую строку res, встречающееся количество раз.
    • Иначе Если str[i] больше, чем равно 'a' и меньше, чем равно 'z', а small[str[i]-'a'] равно i , тогда инициализация переменной происходит как str[i]- 'a' и добавьте str[i] в результирующую строку res, встречающееся количество раз.
    • Иначе Если str[i] больше, чем равно 'A' и меньше, чем равно 'Z', а Capital[str[i]-'0'] равно i , тогда инициализация переменной происходит как str[i]- 'A' и добавить str[i] в результирующую строку res, встречающееся количество раз.
    • В противном случае добавьте str[i] к результирующей строке res.
  • После выполнения вышеуказанных шагов выведите строку res в качестве ответа.

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


Временная сложность: O(N)
Вспомогательный пробел: O(M) (размер результирующей строки)

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