Форматирование лицензионного ключа

Дана строка S , состоящая только из буквенно-цифровых символов и дефисов. Строка разделена на N + 1 группы с помощью N дефисов. Также задано целое число K .

Мы хотим переформатировать строку S так, чтобы каждая группа содержала ровно K символов, за исключением первой группы, которая может быть короче K, но все равно должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и вы должны преобразовать все строчные буквы в прописные.

Вернуть переформатированную строку.

Примеры:

Input: S = “5F3Z-2e-9-w”, K = 4
Output: “5F3Z-2E9W”
Explanation: The string S has been split into two parts,  
each part has 4 characters. 
Note that two extra dashes are not needed and can be removed.

Input: S = “2-5g-3-J”, K = 2
Output: “2-5G-3J”
Explanation: The string s has been split into three parts,  
each part has 2 characters except the first part 
as it could be shorter as mentioned above

Наивный подход: чтобы решить проблему, следуйте следующей идее:

• We will have a Greedy approach in which we will create a temporary string with only the alphanumeric characters(but in reverse) and then add the dashes after every K step.
• The reversal is necessary at the beginning because each group contains exactly K characters, except for the first group as mentioned in the problem.

Следуйте инструкциям, чтобы решить проблему:

• Создайте временную пустую строку и вставьте только те символы (в верхнем регистре), которые отличаются от '-' .
• Теперь переверните полученную строку. Кроме того, создайте строку ' ans' для хранения окончательной строки.
• Выполните итерацию по строке, и всякий раз, когда символы «K» вставляются в «ans», вставляйте тире «-» в строку.
• Верните ' ans' в качестве результата.

Ниже приведена реализация для решения проблемы:

Эффективный подход: для решения проблемы следуйте следующей идее:

• Without creating any other string we will move all the dashes to the front and remove them then we will make use of the mathematical formula to calculate the number of dashes at the right of all the alphanumeric characters.
• Number of Dashes=(Total alphanumeric elements)/(number of elements in every group)

Formula:

Number of Dashes at any step = (Total alphanumeric elements to the right of the current index) / (number of elements in every group)

Следуйте инструкциям, чтобы решить проблему:

• Выполните итерацию с конца строки и переместите все буквенно-цифровые символы в конец строки.
• Удалите все тире с самого начала.
• Подсчитайте количество тире (с округлением вверх), которое будет присутствовать в окончательной строке, и добавьте его к исходной строке.
• Повторяйте спереди и в зависимости от количества тире, которые будут присутствовать до этого символа, переместите символ на это количество в левом направлении.
• Удалите все лишние тире, которые накопились бы в начале строки
• Верните строку после всех изменений в качестве ответа.

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

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