# 880. Decoded String at Index

{% hint style="info" %}
In general, when a decoded string is equal to some word with `size` length repeated some number of times (such as `apple` with `size = 5` repeated 6 times), the answer is the same for the index `K` as it is for the index `K % size`.

We can use this insight by working backwards, keeping track of the size of the decoded string. Whenever the decoded string would equal some `word` repeated `d` times, we can reduce `K` to `K % (word.length)`.
{% endhint %}

```java
class Solution {
    public String decodeAtIndex(String s, int k) {
        //the length of decoded string until index i;
        long l=0;
        int i=0;
        for(; l<k; i++){
           l=(Character.isDigit(s.charAt(i))) ? l*(s.charAt(i)-'0') : l+1; 
        }
        
        // now l>=k
        // make i to previous position
        // reduce the lenth l until l==k, or k==0;
        for(i--; i>=0; i--){
            if(Character.isDigit(s.charAt(i))){
                long size = l/(s.charAt(i)-'0');
                k%=size;
                l=size;
            }else{
                // is letter
                if(k==0 ||k==l){
                    return ""+s.charAt(i);
                }else{
                    l--;
                }
            }
        }
        return "";
    }
}
```
