Decoded String at Index : Array + math

Medium — Leetcode: https://leetcode.com/problems/decoded-string-at-index/solution/

An encoded string S is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

• If the character read is a letter, that letter is written onto the tape.
• If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.

Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

Example 1:

Input: S = "leet2code3", K = 10
Output: "o"
Explanation: 
The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10th letter in the string is "o".

Example 2:

Input: S = "ha22", K = 5
Output: "h"
Explanation: 
The decoded string is "hahahaha".  The 5th letter is "h".

Example 3:

Input: S = "a2345678999999999999999", K = 1
Output: "a"
Explanation: 
The decoded string is "a" repeated 8301530446056247680 times.  The 1st letter is "a".

Constraints:

• 2 <= S.length <= 100
• S will only contain lowercase letters and digits 2 through 9.
• S starts with a letter.
• 1 <= K <= 10^9
• It’s guaranteed that K is less than or equal to the length of the decoded string.
• The decoded string is guaranteed to have less than 2^63 letters.

Solution

Intuition :Work Backwards

We dont actually need to constuct the whole string to be able to do this better. ALl we need is that index of the character to get the value from the original string itself.

If we have a decoded string like appleappleappleappleappleapple and an index like K = 24, the answer is the same if K = 4.

Explaination : Here we did apple ( size 5) repeated 6 times resulting in 5*6=30 character long string. But this 30 characters are 6 times the same original string Apple. The index of “l” in apple is 4. And the index of “l” in apple repeated 6 times are [4, 5 * 1 +4 = 9, 5*2 +4 = 14, 5*3 +4 = 19, 5 * 4 + 4 = 24 and 5 * 5 +4 = 29] ,

In general, when a decoded string is equal to some word with size length repeated some number of times (such as apple with 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 wordrepeated d times, we can reduce K to K % (word.length).

Algorithm

1. First, find the length of the decoded string.
2. After, we’ll work backwards, keeping track of size: the length of the decoded string after parsing symbols S[0], S[1], ..., S[i].
3. If we see a digit S[i], it means the size of the decoded string after parsing S[0], S[1], ..., S[i-1] will be size / Integer(S[i]).
4. If we see a character, it means the size after decoding this character is size - 1.

Code:

class Solution:
    def decodeAtIndex(self, S: str, K: int) -> str:
        size = 0
        # Find size = length of decoded string
        for c in S:
            if c.isdigit():
                size *= int(c)
            else:
                size += 1
        # print(size)
        # print(K)
        # print("*****")
        for c in reversed(S):
            
            K %= size
            # print(K, size)
            if K == 0 and c.isalpha():
                return c
if c.isdigit():
                size /= int(c)
            else:
                size -= 1

Example

Input:

"leet2code3"
10

Stdout

36
10
*****
*****
10 36
*****
10.0 12.0
*****
10.0 11.0
*****
0.0 10.0

Result

"o"