Лексикографически наименьшая строка, образованная повторным удалением символа из подстроки 10.

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

Для заданной двоичной строки S длины N задача состоит в том, чтобы найти лексикографически наименьшую строку, образованную после изменения строки путем выбора любой подстроки «10» и удаления любого символа из этой подстроки любое количество раз.

Примеры:

Input: S = “0101”
Output: 001
Explanation:
Removing the S[1](=1) from the substring, “10” over the range [1, 2] modifies the string S to “001”, which is the smallest.

Input: S =”11001101″
Output: 0001
Explanation:
One possible way to obtain Lexicographically the smallest string is:

  1. Removing the  S[1](=1)  from the substring, “10” over the range [1, 2] modifies the string S as S = “1001101”.
  2. Removing the  S[0](=1)  from the substring, “10” over the range [0, 1] modifies the string S as S = “001101”.
  3. Removing the  S[3](=1)  from the substring, “10” over the range [3, 4] modifies the string S as S = “00101”.
  4. Removing the  S[2](=1)  from the substring, “10” over the range [2, 3] modifies the string S as S = “0001”.
  5. Now any character can not be removed.

Therefore, the lexicographically smallest obtained string is “0001”.

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  • Можно заметить, что символ « 1 » после последнего нуля нельзя удалить, так как невозможно найти подстроку « 10 ».
  • Лексикографически самая маленькая строка будет содержать столько нулей, сколько может быть перед первой.
  • Можно заметить, что каждую « 1 » можно удалить, если после нее стоит хотя бы один « 0 ».
  • Таким образом, идея состоит в том, чтобы удалить из строки все единицы до последнего встречающегося ' 0 '.

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте две переменные, скажем, ans и LastZe, для хранения результирующей строки и индекса последнего встречающегося ' 0 '.
  • Перебрать символы строки S , используя переменную i , а затем, если S[i] равно ' 0 ', присвоить i LastZe.
  • Перебрать символы строки S , используя переменную i , и выполнить следующие операции:
    • Если S[i] = '0' и i ≤ LastZe, то добавьте S[i] к ответу.
    • В противном случае, если i > LastZe, добавьте S[i] к ans .
  • Наконец, после выполнения вышеуказанных шагов, напечатайте результат как an .

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

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

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