880. Decoded String at Index

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).

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 "";
    }
}