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 written d - 1 more times in total.


Given an integer k, return the kth letter (1-indexed) in the decoded string.

&nbsp;
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".


&nbsp;
Constraints:


	2 &lt;= s.length &lt;= 100
	s consists of lowercase English letters and digits 2 through 9.
	s starts with a letter.
	1 &lt;= k &lt;= 109
	It is guaranteed that k is less than or equal to the length of the decoded string.
	The decoded string is guaranteed to have less than 263 letters.


class Solution:
    def decodeAtIndex(self, S: str, K: int) -> str:
        idx = {}
        acclens = [0]
        prevd = 1
        j = 0
        for i, c in enumerate(S + '1'):
            if c.isalpha():
                idx[acclens[-1] * prevd + j] = i
                j += 1
            else:
                acclens.append(acclens[-1] * prevd + j)
                prevd = int(c)
                j = 0
        k = K - 1
        for al in reversed(acclens[1:]):
            k %= al
            if k in idx:
                return S[idx[k]]
        return None  # should never reach this
class Solution {
    public String decodeAtIndex(String s, int k) {
        long sz = 0;
        for (char ch : s.toCharArray()){ // total length
            sz = Character.isDigit(ch)? sz * (ch - '0') : ++sz;
        }
        --k; // make it 0 index based.
        for (int i = s.length() - 1; true; i--){
            if (Character.isLetter(s.charAt(i)) && --sz == k){ // found!
                return ""+s.charAt(i);
            }else if(Character.isDigit(s.charAt(i))){
                sz /= (s.charAt(i) - '0');
                k %= sz; // we are at the end of a multplied string, we can mod k with sz.
            }
        }
    }
}
class Solution {
public:
    string decodeAtIndex(string s, int k) {
        k--;
        struct op { string s; size_t mult; size_t total; };
        vector<op> v;
        size_t total = 0;
        for (auto c : s) {
            if (isalpha(c)) {
                if (v.empty() || v.back().mult > 1)
                    v.push_back({"", 1, total});
                v.back().s += c;
                v.back().total = ++total;
            } else {
                size_t m = c-'0';
                v.back().mult *= m;
                v.back().total = total *= m;
            }
            if (total > k) break;
        }
        while (!v.empty()) {
            auto [s, mult, total] = v.back();
            v.pop_back();
            size_t part = total / mult;
            k %= part;
            if (size_t i = k-part+s.size(); i < s.size())
                return {s[i]};
        }
        return "#";
    }
};
var decodeAtIndex = function(s, k) {
    let len=0;
    let isDigit=false

    for(let v of s){
        if(v>='0'&&v<='9'){
            len*=+v
            isDigit=true
        }else{
            len++
            if(len===k&&!isDigit){
                return s[k-1]
            }
        }
    }

    for(let i=s.length-1;i>=0;i--){
        const v=s[i]
        if(v>='0'&&v<='9'){
            len=Math.ceil(len/+v) // Math.floor() wont work because we endup leaving few strings
            k%=len
        }else{
            if(k===0||k===len){
                    return v
               }
            len--
        }
    }
};
Decoded String at Index