Code Implementation

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        size = 0
        # First, find the length of the decoded string
        for c in s:
            if c.isdigit():
                size *= int(c)
            else:
                size += 1

        for c in reversed(s):
            k %= size
            if k == 0 and c.isalpha():
                return c
            if c.isdigit():
                size //= int(c)
            else:
                size -= 1

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

class Solution {
    public String decodeAtIndex(String s, int k) {
        long size = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                size *= c - '0';
            } else {
                size++;
            }
        }
        for (int i = s.length() - 1; i >= 0; --i) {
            k %= size;
            char c = s.charAt(i);
            if (k == 0 && Character.isLetter(c)) {
                return Character.toString(c);
            }
            if (Character.isDigit(c)) {
                size /= c - '0';
            } else {
                size--;
            }
        }
        return "";
    }
}

var decodeAtIndex = function(s, k) {
    let size = 0;
    for (let c of s) {
        if (/\d/.test(c)) {
            size *= Number(c);
        } else {
            size += 1;
        }
    }
    for (let i = s.length - 1; i >= 0; --i) {
        k %= size;
        if (k === 0 && /[a-zA-Z]/.test(s[i])) {
            return s[i];
        }
        if (/\d/.test(s[i])) {
            size = Math.floor(size / Number(s[i]));
        } else {
            size -= 1;
        }
    }
};

Problem Description

You are given a string s that encodes letters and digits. The string is decoded by reading left to right: when you see a letter, it is written as-is; when you see a digit d, the entire current decoded string is repeated d times.

For example, s = "leet2code3" decodes to "leetleetcodeleetleetcodeleetleetcode".

Given an integer k, return the k-th letter in the decoded string. It is guaranteed that k is valid (1-based index), and the decoded string is large enough.

• There is only one valid answer for each input.
• You do not actually need to build the entire decoded string in memory.

Thought Process

At first, you might think to actually build the decoded string, then just return the k-th character. However, with large input strings and digits, the decoded output can be huge (trillions of characters), making this approach impractical.

Instead, we need to find a way to determine the k-th letter without building the whole string. The key is to simulate the decoding process in reverse, leveraging the way repetitions expand the string. By tracking the current length and working backwards, we can "skip" large blocks efficiently.

This shift from brute-force generation to mathematical reasoning is crucial for handling large inputs efficiently.

Solution Approach

• Step 1: Compute the Decoded Length
  • Iterate through s from left to right.
  • If a character is a letter, increment a size counter.
  • If a character is a digit d, multiply size by d.
  • This gives the total length of the fully decoded string.
• Step 2: Work Backwards to Find the k-th Character
  • Iterate through s from right to left.
  • At each step, set k = k % size. If k == 0 and the character is a letter, that's our answer.
  • If the character is a digit d, divide size by d (undoing the previous multiplication).
  • If it's a letter, decrement size by 1.
• This process efficiently "rewinds" the decoding, mapping k back through the repeated expansions to the original character.

We use this approach because it avoids actually constructing the massive decoded string, instead using math to trace k to its source.

Example Walkthrough

Let's use s = "leet2code3" and k = 10.

1. Compute Decoded Length:
   • l → size = 1
   • e → size = 2
   • e → size = 3
   • t → size = 4
   • 2 → size = 8 (4 * 2)
   • c → size = 9
   • o → size = 10
   • d → size = 11
   • e → size = 12
   • 3 → size = 36 (12 * 3)

   Final decoded length is 36.

2. Work Backwards:
   • Start at last char ('3'), size=36, k=10
   • '3' is digit: size = 12 (36 / 3), k = 10 % 36 = 10
   • 'e' is letter: size = 11, k = 10 % 12 = 10
   • 'd' is letter: size = 10, k = 10 % 11 = 10
   • 'o' is letter: size = 9, k = 10 % 10 = 0
   • 'c' is letter: size = 8, k = 0 % 9 = 0
   • '2' is digit: size = 4 (8 / 2), k = 0 % 8 = 0
   • 't' is letter: size = 3, k = 0 % 4 = 0
   • 'e' is letter: size = 2, k = 0 % 3 = 0
   • 'e' is letter: size = 1, k = 0 % 2 = 0
   • 'l' is letter: size = 0, k = 0 % 1 = 0

   When we reach 'o', k == 0 and it's a letter, so the answer is 'o'.

Time and Space Complexity

• Brute-force approach:
  • Time: O(N * decoded length), where N is the length of s; decoded length can be huge.
  • Space: O(decoded length), since we build the whole string.
• Optimized approach (current solution):
  • Time: O(N), since we scan s twice (forward and backward).
  • Space: O(1), only a few variables are used; no big string is built.

This makes the optimized solution feasible even for very large decoded strings.

Summary

The main insight is that we don't need to actually decode the string to find the k-th letter. By tracking the decoded string's length and reversing the decoding process, we can mathematically map k back to its source character in s. This approach is both elegant and efficient, handling even massive expansions with ease.