Decode String

#APPROACH 1
'''
Using stack:
Time: O(len of decoded string)
Space: O(len of encoded string)

Intuition: To decode the string:
1. COPY ALPHABETS AS IT IS
2. ON DIGITS: FIND THE NUMERIC VALUE OF SEQUENCE OF CONSECUTIVE DIGITS (THEY WILL BE ENDED BY OPENING SQUARE BRACKET AND USED IN CASE 4 IN NEXT ITERATION)
3. ON ']', SUFFIX HAS TO BE REPEATED,
   WHERE: STARTING POINT OF SUFFIX = POSITION OF CHARACTER IN RES FOLLOWING THE MATCHING OPENING BRACKET OF ']' (IN THE ORIGINAL STRING), AND
          NUMBER OF REPETITION = NUMERIC VALUE OF DIGITS PRECEEDING THE MATCHING OPENING SQUARE BRACKET. - 1(REASON EXPLAINED IN CODE)
4. IN ORDER TO FIND THE MATCHING SQUARE OPENING BRACKET AND ITS RELATED INFO(GIVEN IN ABOVE POINT), USE STACK ( AS DONE IN PROBLEM OF WELL-FORMEDNESS OF PARENTHESIS).
   THUS ON '[' PUSH TUPLE CONSISTING OF INTERGRAL VALUE FOUND AT CASE 2 IN PREVIOUS ITERATION(AS '[' IS ALWAYS PRECEEDED BY DIGITS) AND, CURRENT LENGTH OF RESULT (AS '[' IS ALWAYS FOLLOWED BY ALPHABETS AND THUS CURRENT LENGTH OF RESULT WOULD BE THE INDEX OF CHARACTER FOLLOWING '[' AD REQUIRED IN CASE 3)
'''
class Solution:
    def decodeString(self, s: str) -> str:
        stack = deque()
        res = ""
        rs = 0

        i, n, dig = 0, len(s), ""
        while i < n:
            if s[i].isalpha():
                res += s[i] #alphabets copied as it is and length incremented
                rs += 1

            elif s[i].isdigit():
                dig += s[i] #keep track of consecutive digits before '['(it is the no. of times following enclosed content has to be repeated)

            elif s[i] == '[':
                stack.append((int(dig)-1, rs)) #stack contains two info related to '[': 1. Numeric value of digits before it minus one(as the content to be repeated will be already written once by first if case), and the current length of result(as it is origin point for the repetition)
                dig = "" #the sequence of digits end at '[', thus reset

            else: #s[i] == ']'
                ele = stack.pop()
                cyc = (rs - ele[1]) #length of the suffix starting at ele[1] of res to be repeated ele[0] times
                for _ in range(cyc * ele[0]):
                    res += res[-cyc]
                    rs += 1
            i += 1

        return res


#APPROACH 2: Recursive implementation of the same (using dfs)
'''
class Solution:
    idx = -1
    def decodeString(self, s: str) -> str:
        self.idx += 1
        res, dig = "", ""
        while self.idx < len(s):
            if s[self.idx].isalpha():
                res += s[self.idx]

            elif s[self.idx].isdigit():
                dig += s[self.idx]

            elif s[self.idx] == '[':
                res += (self.decodeString(s)) * int(dig)
                dig = ""

            else:
                return res

            self.idx += 1

        return res
'''