880. Decoded String at Index

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".

Note:

2 <= S.length <= 100
S will only contain lowercase letters and digits 2 through 9.
S starts with a letter.
1 <= K <= 10^9
The decoded string is guaranteed to have less than 2^63 letters.

Solution 1: Naïve

class Solution:
    def decodeAtIndex(self, S: str, K: int) -> str:
        
        result = []
        index = 0
        
        while len(result) < K:
            if S[index].isalpha():
                result.append(S[index])
            else:
                temp = deepcopy(result)
                for i in range(int(S[index]) - 1):
                    result.extend(temp)
                    
            index += 1
                
        return result[K - 1]

This was my original and naive solution. I simply went through the process of decrypting the strings, like the problem described. I looped through the string, and if I arrived at a latter, I added it to the result string. If I arrived at a number, I multiplied the string out that many times. I terminated the algorithm once the resulting string was long enough to find the value.

This solution is fine for test cases where the index we want to find is small, like 10 or 20. However, this solution failed a test case where k = 222280369. This led me to believe that this naive solution is not efficient enough to work for larger test cases. Basically, we had to figure out how to calculate values in the final string, without actually building the entire string.

Solution 2: 🤯

class Solution:
    def decodeAtIndex(self, S: str, K: int) -> str:
        
        size = 0
        
        for c in S:
            if c.isalpha():
                size += 1
            else:
                size *= int(c)
                
        for c in reversed(S):
            K %= size
            if K == 0 and c.isalpha():
                return c

            if c.isdigit():
                size /= int(c)
            else:
                size -= 1

This solution is so hard to comprehend for me, I basically stole it from the published Leetcode solution. Basically we take advantage of the fact that with a known, repeated pattern, the K’th character in the string will be equal to the k % pattern_size character.

For example, say we have the string "banana3" and we want the 11th character of the final string, so K = 11. We could calculate the entire final string, which would be "bananabananabanana" and loop through to the 11th character. However, this fails if we had a string like "banana12487425023487501", where it’s just way too long to calculate.

Instead, we can use modulus to reduce the index that we’re looking for. The len("banana") is 6, and the character at index K is the same as the character at index K % 6 (try it!).

The solution uses this property to calculate the index that we’ll need in the original string. The Leetcode solution describes it a little better, I would read that if still confused (like I am).

Solution 1: Naïve

Solution 2: 🤯

Try it on Leetcode