# LeetCode 880: Decoded String at Index

## Problem Restatement

We are given an encoded string `s` and an integer `k`.

The string is decoded from left to right using these rules:

| Character | Meaning |
|---|---|
| Letter | Append the letter to the tape |
| Digit `d` | Repeat the entire current tape `d - 1` more times |

Return the `k`th character of the final decoded string, using 1-based indexing.

The decoded string can be extremely large, so we must not build it directly. The problem guarantees that `k` is within the decoded length, and the decoded length is less than `2^63`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Encoded string `s` and integer `k` |
| Output | The `k`th decoded character |
| Indexing | 1-based |
| Digits | Only `2` through `9` |
| String | Starts with a lowercase English letter |

Function shape:

```python
def decodeAtIndex(self, s: str, k: int) -> str:
    ...
```

## Examples

Example 1:

```text
Input: s = "leet2code3", k = 10
Output: "o"
```

The decoded string is:

```text
leetleetcodeleetleetcodeleetleetcode
```

The 10th character is `"o"`.

Example 2:

```text
Input: s = "ha22", k = 5
Output: "h"
```

Decode step by step:

```text
h
ha
haha
hahahaha
```

The 5th character is `"h"`.

Example 3:

```text
Input: s = "a2345678999999999999999", k = 1
Output: "a"
```

The decoded string is a huge repetition of `"a"`, so the first character is `"a"`.

## First Thought: Build the Decoded String

The direct approach is to simulate the tape.

When we see a letter, append it.

When we see a digit, repeat the whole current string.

```python
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        decoded = ""

        for ch in s:
            if ch.isdigit():
                decoded *= int(ch)
            else:
                decoded += ch

        return decoded[k - 1]
```

This matches the decoding rule, but it fails for large inputs.

For example:

```text
s = "a2345678999999999999999"
```

The decoded string is far too large to store in memory.

## Problem With Direct Decoding

The encoded string has length at most `100`, but the decoded string may contain billions or trillions of characters.

So the encoded input is small, but the expanded output can be enormous.

We only need one character. We should track lengths and positions instead of constructing the decoded string.

## Key Insight

First compute the length of the decoded string.

Let `size` be the decoded length after reading some prefix of `s`.

When we read a letter:

```python
size += 1
```

When we read a digit `d`:

```python
size *= d
```

After this forward pass, `size` is the total decoded length.

Then work backward through `s`.

The idea is to reverse the encoding process.

If the current character is a digit `d`, then the current decoded tape was created by repeating the previous tape `d` times.

So if the current length is `size`, the previous length was:

```python
size // d
```

The target index `k` can be mapped back into one copy using modulo.

If the current character is a letter, then it was appended at the end of the previous tape.

If `k` points to the end of the current tape, that letter is the answer.

## Algorithm

First pass:

1. Set `size = 0`.
2. For each character `ch` in `s`:
   1. If `ch` is a digit, multiply `size` by that digit.
   2. Otherwise, add `1` to `size`.

Second pass, from right to left:

1. Reduce `k` using:

```python
k %= size
```

2. If `k == 0` and the current character is a letter, return it.
3. If the current character is a digit `d`, undo the repeat:

```python
size //= d
```

4. If the current character is a letter, undo the append:

```python
size -= 1
```

## Walkthrough

Use:

```text
s = "leet2code3"
k = 10
```

First compute decoded lengths:

| Character | Operation | Size |
|---|---|---:|
| `l` | add letter | 1 |
| `e` | add letter | 2 |
| `e` | add letter | 3 |
| `t` | add letter | 4 |
| `2` | repeat tape twice | 8 |
| `c` | add letter | 9 |
| `o` | add letter | 10 |
| `d` | add letter | 11 |
| `e` | add letter | 12 |
| `3` | repeat tape three times | 36 |

Now go backward.

At size `36`, the 10th character in the full string is the same as the 10th character inside one copy of length `12`, because the final `3` repeats a length-12 tape.

Then we inspect backward through `code`.

When we reach the letter `o`, the current size is `10`.

Since:

```python
10 % 10 == 0
```

and the current character is a letter, the answer is `"o"`.

## Correctness

The forward pass computes the decoded length after each prefix of the encoded string.

For a letter, the decoded tape gains one character, so increasing `size` by `1` is correct.

For a digit `d`, the current tape is repeated until there are `d` total copies, so multiplying `size` by `d` is correct.

Now consider the reverse pass.

At any reverse step, `size` is the decoded length produced by the prefix ending at the current character. The target `k` refers to a position inside that decoded tape.

If the current character is a digit `d`, the current tape consists of `d` identical copies of the previous tape. Therefore, position `k` in the current tape corresponds to position `k % previous_size` in the previous tape, with remainder `0` meaning the last character of a copy. Since `previous_size = size // d`, dividing `size` by `d` correctly restores the previous tape length.

If the current character is a letter, then that letter is the final character of the current tape. If `k % size == 0`, then `k` points exactly to this final character, so the current letter is the answer. Otherwise, the target lies earlier in the tape, and reducing `size` by `1` correctly removes this appended letter from consideration.

The loop applies these reverse steps until it finds the unique letter that occupies the requested decoded position. Therefore, the algorithm returns the correct character.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | One forward pass and one backward pass over `s` |
| Space | `O(1)` | Only `size`, `k`, and loop variables are stored |

## Implementation

```python
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        size = 0

        for ch in s:
            if ch.isdigit():
                size *= int(ch)
            else:
                size += 1

        for ch in reversed(s):
            k %= size

            if k == 0 and ch.isalpha():
                return ch

            if ch.isdigit():
                size //= int(ch)
            else:
                size -= 1

        return ""
```

## Code Explanation

We first compute the decoded length:

```python
size = 0

for ch in s:
    if ch.isdigit():
        size *= int(ch)
    else:
        size += 1
```

This does not build the decoded string. It only records how long the decoded string would be.

Then we walk backward:

```python
for ch in reversed(s):
```

At each step, we map `k` into the current decoded length:

```python
k %= size
```

If `k == 0` and the current character is a letter, then the requested position is exactly this letter:

```python
if k == 0 and ch.isalpha():
    return ch
```

If the current character is a digit, we undo the repetition:

```python
size //= int(ch)
```

If the current character is a letter, we undo the append:

```python
size -= 1
```

The final `return ""` is only a fallback. Valid LeetCode input always returns inside the loop.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.decodeAtIndex("leet2code3", 10) == "o"
    assert s.decodeAtIndex("ha22", 5) == "h"
    assert s.decodeAtIndex("a2345678999999999999999", 1) == "a"
    assert s.decodeAtIndex("abc3", 8) == "b"
    assert s.decodeAtIndex("y959q969u3hb22odq595", 222280369) == "y"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"leet2code3", 10` | Standard mixed letters and repeats |
| `"ha22", 5` | Repeated tape more than once |
| Large repeated `"a"` | Huge decoded length without building string |
| `"abc3", 8` | Position inside repeated copy |
| Long encoded string | Checks large `k` and multiple reverse reductions |