##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/880.html

# 880. Decoded String at Index (Medium)

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.

Related Topics:
Stack

## Solution 1.

• class Solution {
public String decodeAtIndex(String S, int K) {
TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();
long count = 0;
int length = S.length();
int index = 0;
while (index < length && count < K) {
char c = S.charAt(index);
if (Character.isLetter(c))
count++;
else
count *= c - '0';
map.put(count, index);
index++;
}
long position = K;
while (!map.containsKey(position) || Character.isDigit(S.charAt(map.get(position)))) {
long key = map.floorKey(position - 1);
position %= key;
if (position == 0)
position = key;
}
int strIndex = map.get(position);
char letter = S.charAt(strIndex);
return String.valueOf(letter);
}
}

• // OJ: https://leetcode.com/problems/decoded-string-at-index/
// Time: O(S)
// Space: O(S)
class Solution {
public:
string decodeAtIndex(string S, int K) {
vector<tuple<string, int, long>> v;
long N = S.size(), len = 0;
--K;
for (int i = 0; i < N; ) {
string s;
while (i < N && isalpha(S[i])) s += S[i++];
int n = S[i++] - '0';
len += s.size();
v.emplace_back(s, n, len);
len *= n;
if (len > K) break;
}
for (int i = v.size() - 1; i >= 0; --i) {
auto [s, n, len] = v[i];
K %= len;
if (i == 0) return string(1, s[K % s.size()]);
else if (K >= len - s.size()) return string(1, s[K - (len - s.size())]);
}
return "";
}
};

• class Solution(object):
def decodeAtIndex(self, S, K):
"""
:type S: str
:type K: int
:rtype: str
"""
size = 0
for c in S:
if c.isdigit():
size *= int(c)
else:
size += 1

for c in reversed(S):
K %= size
if K == 0 and c.isalpha():
return c
if c.isdigit():
size /= int(c)
else:
size -= 1