Зашифровать строку – 2

Для данной строки S , состоящей из N строчных букв английского алфавита, также дается, что строка шифруется путем первой замены каждой подстроки строки, состоящей из одного и того же символа, конкатенацией этого символа и шестнадцатеричным представлением размера подстроки и затем, почитав всю строку, задача состоит в том, чтобы найти зашифрованную строку.

Примечание. Все шестнадцатеричные буквы следует преобразовать в строчные.

Примеры:

Input: S = “aaaaaaaaaaa”
Output: ba  
Explanation:

1. First convert the given string to “a11” i.e. write, character along with its frequency.
2. Then, change “a11” to “ab” because 11 is b in hexadecimal.
3. Then, finally reverse the string i.e “ba”.

Input: S = “abc”
Output: 1c1b1a

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

• Инициализировать пустую строку сказать, чтобы сохранить ответ.
• Переберите символы строки S, используя переменную i , и выполните следующие шаги:
  • Найдите количество подстроки с тем же символом S[i], начиная с индекса i , и сохраните его в переменной, скажем, count .
  • Теперь преобразуйте количество в шестнадцатеричное представление и добавьте символ S[i] вместе с его шестнадцатеричным представлением частот.
• Наконец, переверните строку и затем распечатайте ее.

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

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