# Decoded String at Index
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/decoded-string-at-index)
Canonical: https://scaleengineer.com/dsa/problems/decoded-string-at-index
**Data structures:** String, Stack
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe), [National Instruments](https://scaleengineer.com/companies/national-instruments)
---
## Problem
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_.

**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` consists of lowercase English letters and digits `2` through `9`.
* `s` starts with a letter.
* `1 <= k <= 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.

# Approaches
## Brute-Force Simulation
This approach directly simulates the decoding process described in the problem. It builds the entire decoded string in memory and then retrieves the character at the k-th position. While this is the most straightforward way to think about the problem, it is not feasible given the constraints. The length of the decoded string can grow exponentially, quickly exceeding memory and time limits.
**Time:** O(L), where L is the length of the fully decoded string. String concatenation and building can be very slow for large strings. · **Space:** O(L), where L is the length of the fully decoded string. This is the major drawback, as L can be up to 2^63 - 1.
**Pros:** Simple to understand and implement.; Follows the problem description literally.
**Cons:** Extremely inefficient for the given constraints.; Will result in `OutOfMemoryError` as the decoded string can have up to 2^63 - 1 characters.; Will result in `TimeLimitExceeded` due to the massive number of append operations.
### Explanation
The idea is to use a mutable string, like Java's `StringBuilder`, to construct the decoded string. We process the encoded string `s` character by character. When we encounter a letter, we append it. When we see a digit `d`, we duplicate the current content of our `StringBuilder` `d-1` times. This process continues until we have processed all of `s`. Finally, we access the character at the `k-1` index (since `k` is 1-indexed) of the resulting string.

```java
class Solution {
    public String decodeAtIndex(String s, int k) {
        StringBuilder decodedString = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                decodedString.append(c);
            } else {
                long d = c - '0';
                String currentTape = decodedString.toString();
                for (int i = 0; i < d - 1; i++) {
                    decodedString.append(currentTape);
                    // A small optimization could be to check if length > k here,
                    // but it doesn't save it from memory/time issues on large inputs.
                }
            }
        }
        return String.valueOf(decodedString.charAt(k - 1));
    }
}
```
This code will fail on examples like `s = "a2345678999999999999999"` because the length of the decoded string becomes astronomically large.
### Algorithm
- Initialize an empty `StringBuilder` to act as the tape.
- Iterate through each character of the input string `s`.
- If the character is a letter, append it to the `StringBuilder`.
- If the character is a digit `d`, take the current string in the `StringBuilder` and append it `d-1` more times.
- After iterating through the entire string `s`, the `StringBuilder` will contain the fully decoded string.
- Return the character at index `k-1` from the `StringBuilder`.

## Optimal Two-Pass Approach (Working Backwards)
Since building the string is infeasible, we can solve this problem by working backwards. The core idea is to first calculate the total length of the decoded string. Then, we iterate backwards through the encoded string `s`, reducing the size and `k` at each step until we pinpoint the `k`-th character. This avoids creating the string itself, making it extremely efficient.
**Time:** O(N), where N is the length of the input string `s`. We perform two linear passes over the string `s`. · **Space:** O(1). We only use a few variables (`size`, `i`, `k`) to store state, regardless of the input size.
**Pros:** Extremely efficient, runs in linear time with respect to the input string `s` length.; Uses constant extra space, making it suitable for all constraints.; Handles gigantic decoded strings and large `k` values effortlessly.
**Cons:** The logic of working backwards can be less intuitive to grasp initially.
### Explanation
This approach cleverly avoids generating the massive decoded string. It works in two passes.

**First Pass:** We calculate the total length of the decoded string. We iterate through `s`, updating a `size` variable. If we see a letter, we increment `size`. If we see a digit `d`, we multiply `size` by `d`. We use a `long` for `size` to prevent overflow.

**Second Pass:** We iterate backwards from the end of `s`. At each step, we know the `size` of the string decoded up to that point. We want to find the `k`-th character. The key insight is that the `k`-th character in a string of length `L` repeated `d` times is the same as the `(k-1) % L + 1`-th character in the original string of length `L`. We can simplify this using `k %= size`. By repeatedly applying this logic and 'undoing' the operations (division for a digit, decrement for a letter), we can trace `k` back to the character it corresponds to in the original non-repeated parts of the string.

```java
class Solution {
    public String decodeAtIndex(String s, int k) {
        long size = 0;
        int n = s.length();

        // Pass 1: Calculate the total size of the decoded string.
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                size *= (c - '0');
            } else {
                size++;
            }
        }

        // Pass 2: Work backwards to find the k-th character.
        for (int i = n - 1; i >= 0; i--) {
            char c = s.charAt(i);
            // Cast k to long for the modulo operation to be safe.
            long k_long = k;
            k_long %= size;

            if (k_long == 0 && Character.isLetter(c)) {
                // This is the character we are looking for.
                // k_long == 0 means we are at the last character of the current segment.
                return String.valueOf(c);
            }

            if (Character.isDigit(c)) {
                // If it's a digit, we undo the multiplication.
                size /= (c - '0');
            } else {
                // If it's a letter, we undo the addition.
                size--;
            }
            // Update k for the next iteration.
            k = (int) k_long;
        }

        return ""; // Should not be reached given the problem constraints.
    }
}
```
### Algorithm
- **Pass 1: Calculate Decoded String Size**
  - Initialize a `long` variable `size` to 0.
  - Iterate through the encoded string `s` from left to right.
  - If the character `c` is a letter, increment `size` by 1.
  - If the character `c` is a digit `d`, multiply `size` by `d`.
- **Pass 2: Work Backwards to Find the Character**
  - Iterate through the encoded string `s` from right to left (from index `n-1` to `0`).
  - Let the current character be `c`.
  - For each character, first update `k` by taking it modulo the current `size`: `k %= size`.
  - If `c` is a letter:
    - If the updated `k` is 0 (or if `k` was originally a multiple of `size`), this letter is our answer. Return it.
    - Otherwise, this letter is not the one we're looking for. We effectively 'remove' it from the end by decrementing `size`: `size--`.
  - If `c` is a digit `d`:
    - We 'undo' the multiplication by dividing `size` by `d`: `size /= d`.

# Solutions
### Java

```java
class Solution { public String decodeAtIndex ( String s , int k ) { long m = 0 ; for ( int i = 0 ; i < s . length (); ++ i ) { if ( Character . isDigit ( s . charAt ( i ))) { m *= ( s . charAt ( i ) - '0' ); } else { ++ m ; } } for ( int i = s . length () - 1 ;; -- i ) { k %= m ; if ( k == 0 && ! Character . isDigit ( s . charAt ( i ))) { return String . valueOf ( s . charAt ( i )); } if ( Character . isDigit ( s . charAt ( i ))) { m /= ( s . charAt ( i ) - '0' ); } else { -- m ; } } } }
```

### CPP

```cpp
class Solution { public: string decodeAtIndex ( string s , int k ) { long long m = 0 ; for ( char & c : s ) { if ( isdigit ( c )) { m *= ( c - '0' ); } else { ++ m ; } } for ( int i = s . size () - 1 ;; -- i ) { k %= m ; if ( k == 0 && isalpha ( s [ i ])) { return string ( 1 , s [ i ]); } if ( isdigit ( s [ i ])) { m /= ( s [ i ] - '0' ); } else { -- m ; } } } };
```

### Python

```python
class Solution : def decodeAtIndex ( self , s : str , k : int ) -> str : m = 0 for c in s : if c . isdigit (): m *= int ( c ) else : m += 1 for c in s [:: - 1 ]: k %= m if k == 0 and c . isalpha (): return c if c . isdigit (): m //= int ( c ) else : m -= 1
```