Проверить, можно ли сделать строку, состоящую только из a, b, c, пустой, рекурсивно удалив подстроку «abc»

Для заданной строки S размера N , состоящей только из символов ' a ', ' b ' и ' c ', задача состоит в том, чтобы проверить, можно ли сделать данную строку пустой, рекурсивно удалив строку «abc» или нет. Если найдено верно , то выведите «Да» . В противном случае выведите «Нет» .

Примеры:

Input: S = abcabc
Output: Yes
Explanation:
Below are the operations performed to empty the string:

1. Remove the substring S[3, 5] from the string modifies the string S to “abc”.
2. Remove the substring S[0, 2] from the string modifies the string S to “”.

After the above operations, the given string S can be made empty by removing substring “abc”. Therefore, print Yes.

Input: S = abcabcababccc
Output: No

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

• Инициализируйте стек, скажем, Stack для хранения символов заданной строки S .
• Пройдите по заданной строке S и выполните следующие шаги:
  • Если текущий символ ' a ' или ' b ', то поместите его в стек Stack .
  • Если текущий символ — « c », а последние два символа — « b » и « a » соответственно, то извлекается из стека дважды.
  • Если текущий символ ' c ', а последние два символа не ' b ' и ' a ', то данная строка S не может быть сформирована.
• После выполнения вышеуказанных шагов, если стек пуст, то выведите «Да» . В противном случае выведите «Нет» .

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

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