Сложность: hard
Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.
Пример:
Input: s = "11011000"
Output: "11100100"
👨💻 Алгоритм:
1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.
2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.
3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.
😎 Решение:
def makeLargestSpecial(s):
count = i = 0
substrs = []
for j, char in enumerate(s):
count += 1 if char == '1' else -1
if count == 0:
substrs.append('1' + makeLargestSpecial(s[i + 1:j]) + '0')
i = j + 1
Ставь 👍 и забирай 📚 Базу знаний