# 880     Decoded String at Index

## 880. [Decoded String at Index](https://leetcode.com/problems/decoded-string-at-index/description/)

## 1. Question

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".
```

**Note:**

1. `2 <= S.length <= 100`
2. `S`will only contain lowercase letters and digits`2`through`9`.
3. `S`starts with a letter.
4. `1 <= K <= 10^9`
5. The decoded string is guaranteed to have less than`2^63`letters.

## 2. Implementation

**(1) Math**

思路: 一看下最简单的做法就是解析String, 然后找出第K个位置的character。但这种做法其实不需要，因为我们只关心第K个位置的character，我们只要知道解析后的string的总长度，然后从后往前扫一遍输入的String， 当K等于0， 而当前位置的character不是digit，则我们找到第K个character

```java
class Solution {
    public String decodeAtIndex(String S, int K) {
        long len = 0;

        for (char c : S.toCharArray()) {
            if (Character.isDigit(c)) {
                len *= (c - '0');
            }
            else {
                ++len;
            }
        }

        for (int i = S.length() - 1; i >= 0; i--) {
            K %= len;

            char c = S.charAt(i);

            if (K == 0 && c >= 'a' && c <= 'z') {
                return "" + c;
            }

            if (Character.isDigit(c)) {
                len /= (c - '0');
            }
            else {
                --len;
            }
        }
        return  "";
    }
}
```

## 3. Time & Space Complexity

**(1) Math:** 时间复杂度O(n), 空间复杂度O(1)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/stack/880-decoded-string-at-index.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.