Decoded String at Index

medium string stack math

Problem

An encoded string is read left to right: a letter is written once, and a digit d repeats everything decoded so far d times. The decoded string can be enormous, so given the encoding s and an index k (1-based), return the k-th character without materializing the decoding.

Inputs = "leet2code3", k = 10

Output"o"

Decoded: "leetleetcodeleetleetcodeleetleetcode"; position 10 is 'o'.

s (letters and digits 2–9)

k (1-based)

def decode_at_index(s, k):
    size = 0
    for c in s:
        size = size * int(c) if c.isdigit() else size + 1
    for c in reversed(s):
        k %= size
        if k == 0 and c.isalpha():
            return c
        size = size // int(c) if c.isdigit() else size - 1

function decodeAtIndex(s, k) {
  let size = 0;
  for (const c of s)
    size = /\d/.test(c) ? size * (+c) : size + 1;
  for (let i = s.length - 1; i >= 0; i--) {
    const c = s[i];
    k %= size;
    if (k === 0 && /[a-z]/.test(c)) return c;
    size = /\d/.test(c) ? size / (+c) : size - 1;
  }
}

String decodeAtIndex(String s, long k) {
    long size = 0;
    for (char c : s.toCharArray())
        size = Character.isDigit(c) ? size * (c - '0') : size + 1;
    for (int i = s.length() - 1; i >= 0; i--) {
        char c = s.charAt(i);
        k %= size;
        if (k == 0 && Character.isLetter(c)) return String.valueOf(c);
        size = Character.isDigit(c) ? size / (c - '0') : size - 1;
    }
    return "";
}

string decodeAtIndex(string s, long long k) {
    long long size = 0;
    for (char c : s)
        size = isdigit(c) ? size * (c - '0') : size + 1;
    for (int i = s.size() - 1; i >= 0; i--) {
        char c = s[i];
        k %= size;
        if (k == 0 && isalpha(c)) return string(1, c);
        size = isdigit(c) ? size / (c - '0') : size - 1;
    }
    return "";
}

Explanation

The decoded string can be astronomically large, so we never build it. Instead we find the k-th character by reasoning about lengths and repetition, then walking the encoding backwards.

First pass: compute the total decoded size. A letter adds 1 to the length; a digit d means "repeat everything so far d times", so it multiplies the length by d.

Second pass: walk the encoding from the end. The crucial trick is k %= size. Since the string before a digit is repeated, position k in a repeated block is the same character as position k mod size in one copy. Reducing k this way "folds" it back into the un-repeated part.

If at some point k becomes 0 and the current character is a letter, that letter is exactly the one sitting at position k, so we return it. Otherwise we shrink size back: divide by the digit (undo a repeat) or subtract 1 for a letter, and keep going.

Example: s="leet2code3", k=10. The decoded length is 36; folding k with the modulo and walking back lands on the letter 'o'.

Time: O(n) Space: O(1)