Approach 1: Work Backwards
If we have a decoded string like
appleappleappleappleappleapple and an index like
K = 24, the answer is the same if
K = 4.
In general, when a decoded string is equal to some word with
size length repeated some number of times (such as
size = 5 repeated 6 times), the answer is the same for the index
K as it is for the index
K % size.
We can use this insight by working backwards, keeping track of the size of the decoded string. Whenever the decoded string would equal some
d times, we can reduce
K % (word.length).
First, find the length of the decoded string. After, we'll work backwards, keeping track of
size: the length of the decoded string after parsing symbols
S, S, ..., S[i].
If we see a digit
S[i], it means the size of the decoded string after parsing
S, S, ..., S[i-1] will be
size / Integer(S[i]). Otherwise, it will be
size - 1.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.