Decoded String at Index : Array + math

  • If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.
Input: S = "leet2code3", K = 10
Output: "o"
Explanation:
The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10th letter in the string is "o".
Input: S = "ha22", K = 5
Output: "h"
Explanation:
The decoded string is "hahahaha". The 5th letter is "h".
Input: S = "a2345678999999999999999", K = 1
Output: "a"
Explanation:
The decoded string is "a" repeated 8301530446056247680 times. The 1st letter is "a".
  • 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.

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.

  1. After, we’ll work backwards, keeping track of size: the length of the decoded string after parsing symbols S[0], S[1], ..., S[i].
  2. 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]).
  3. If we see a character, it means the size after decoding this character is size - 1.
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
"leet2code3"
10
36
10
*****
*****
10 36
*****
10.0 12.0
*****
10.0 11.0
*****
0.0 10.0
"o"

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store