https://leetcode.com/problems/decoded-string-at-index

Let us iterate over our string S and check lengths of string we have after each step. Let us consider example S = hi2bob3.

1.h, length = 1 2.hi, length = 2 3.hi2, string becomes hihi and length equal to 4. 4.hi2b, string becomes hihib, length equal to 5. 5.hi2bo, string becomes hihibo, length equal to 6. 6.hi2bob, string becomes hihibob, length equal to 7. 7.hi2bob3, string becomes hihibobhihibobhihibob, length equal to 21.

Let us write down all these lengths into array len: if we have letter, we increase previous element by 1, if it is digit, we increase previous element multiplied by this digit.

Now, we need to find letter, imagine we have K = 18. We will traverse our S from the end and check K % lens[i].

  1. 18 < 21, so on this step we do nothing.
  2. 18 % 7 = 4, it means, that string hihibob repeated 3 times and we need to choose element number 4 from this string.
  3. 4 < 6, 4 < 5, so we skip these two steps
  4. Now we have K = 4 and lens[i] = 4, and we make K = 0. We are good, we can stop? Not exactly, the problem, that now we on the place hi2 and we are on digit symbol, so we need to continue.
  5. Now, K = 0 and lens[i] = 2, and also we have string hi so far, so we can stop and answer will be i.

Complexity: time complexity is O(n), space complexity as well. Space complexity can be reduced to O(1), if we do not store lens and only the last one and go back on the fly.

class Solution:
    def decodeAtIndex(self, S, K):
        lens, n = [0], len(S)
        for c in S:
            if c.isdigit():
                lens.append(lens[-1]*int(c))
            else:
                lens.append(lens[-1] + 1)
                
        for i in range(n, 0, -1):
            K %= lens[i]
            if K == 0 and S[i-1].isalpha():
                return S[i-1]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0880