Задача с собеседования в eBay

Дана закодированная строка. Верните её в раскодированном виде.
Правило кодирования: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Гарантируется, что k - целое положительное число.

Считайте, что входная строка всегда корректна: нет лишних пробелов, квадратные скобки сформированы правильно и т.д.. Кроме того, можно считать, что исходные данные не содержат цифр, а цифры используются только для указания числа повторов k. Например, не будет таких входных данных, как 3a или 2[4].
Тестовые примеры сгенерированы так, что длина выходной строки никогда не превысит 10⁵.

Пример 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Пример 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"

Пример 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Ограничения:
1 <= s.length <= 30;
s состоит из строчных английских букв, цифр и квадратных скобок "[]";
s гарантированно является корректным входом;
Все целые числа в s находятся в диапазоне [1, 300].

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Очевидная сложность раскодирования в том, что скобки могут быть вложенными. Сначала должны обрабатываться внутренние скобки, поэтому будем использовать стек для хранения символов и промежуточных результатов.

Итерируемся по строке s:
Добавляем символ в стек, если он не является закрывающей скобкой.
Если же встречаем закрывающую скобку, начинаем собирать подстроку:
Пока верхний эл-т стека не является открывающей скобкой: извлекаем символы из стека и добавляем в начало substring.
Далее открывающую скобку из стека удаляем: мы обработали содержимое внутри скобок, теперь нужно получить число его повторов, находящееся перед открывающей скобкой.
Так как число k может быть многозначным, необходимо извлекать символы до тех пор, пока стек не пуст и верхний эл-т является цифрой.
Преобразовываем k в целое число и умножаем подстроку на него, добавляем результат в стек.
После того, как строка s будет полностью обработана, возвращаем итоговую строку, содержащую объединённые эл-ты стека.

Сложность
O(maxK^countK * n) - по времени (где maxK - максимальное значение k, countK - количество вложенных k значений (уровень вложенности), а n - максимальная длина закодированной строки)
O(n) - по памяти

Код
class Solution:
def decodeString(self, s: str) -> str:
stack = []

for char in s:
if char != "]":
stack.append(char)
else:
substring = ""
while stack[-1] != "[":
substring = stack.pop() + substring
stack.pop()

k = ""
while stack and stack[-1].isdigit():
k = stack.pop() + k
stack.append(int(k) * substring)

return "".join(stack)

@algoses