Decoded String at Index
Medium
You are given an encoded string s. To decode the 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
d, the entire current tape is repeatedly writtend - 1more times in total.
Given an integer k, return the k-th letter (1-indexed) in the decoded string.
For example:
s = "leet2code3", k = 10
The decoded string is "leetleetcodeleetleetcodeleetleetcode". The 10th letter in the string is "o".
s = "ha22", k = 5
The decoded string is "hahahaha". The 5th letter is "h".
s = "a2345678999999999999999", k = 1
The decoded string is "a" repeated a very large number of times. The 1st letter is "a".
Can you implement a function that efficiently finds the k-th letter in the decoded string, given the encoded string s and the index k? Consider edge cases and optimize for both time and space complexity.
Solution
Brute Force Approach
A straightforward approach is to decode the entire string and then return the k-th character. However, this method is inefficient for large decoded string lengths.
Code (Python)
def decode_string_brute_force(s, k):
decoded_string = ""
for char in s:
if char.isalpha():
decoded_string += char
else:
decoded_string *= (int(char) - 1)
return decoded_string[k - 1]
Time Complexity
O(N), where N is the length of the decoded string. This can be very large.
Space Complexity
O(N), for storing the decoded string.
Optimal Approach
A more efficient approach is to work backward from the target index k. We iterate through the encoded string from right to left. If we encounter a digit, we check if k falls within the repeated segment. If so, we can reduce k to its equivalent position in the original segment using the modulo operator. If we encounter a letter, we check if k equals the current length. If it does, we have found the target character.
Edge Cases
- Empty Input String
- Large Values of K
- K = 1
Code (Python)
def decode_string(s, k):
length = 0
for char in s:
if char.isalpha():
length += 1
else:
length *= int(char)
for i in range(len(s) - 1, -1, -1):
char = s[i]
if char.isdigit():
length /= int(char)
k %= length
else:
if k == 0 or k == length:
return char
length -= 1
Time Complexity
O(N), where N is the length of the encoded string.
Space Complexity
O(1), constant space is used.
