Solution Explanation: Decoded String at Index

This problem asks to find the k-th character in a decoded string. The string is encoded such that digits represent repetitions of the preceding substring. A naive approach would fully decode the string, which is computationally expensive for large inputs and large values of k. A more efficient approach involves reverse traversal and modular arithmetic.

Algorithm:

1. Calculate the total length: First, iterate through the encoded string s. If a character is a digit, multiply the current total length by that digit. If it's a letter, increment the total length. This gives us the length m of the fully decoded string.

2. Reverse traversal and modular arithmetic: Iterate through the string from right to left. For each character:

   • Apply the modulo operator (k %= m) to k. This effectively wraps around the decoded string, ensuring we always deal with the correct index.
   • If k becomes 0 and the current character is a letter, that letter is the k-th character, so return it.
   • If the character is a digit, divide the current total length m by that digit (integer division). This accounts for the repetition introduced by the digit.
   • If the character is a letter, decrement m. This reflects that we've moved past one character in the decoded string.

Time Complexity: O(n), where n is the length of the encoded string. We iterate through the string twice (once to calculate the total length and once for the reverse traversal). The operations within each loop are constant time.

Space Complexity: O(1). We use only a constant amount of extra space to store variables.

Code Examples:

The provided code examples in Python, Java, C++, Go, and TypeScript all follow this algorithm. They differ slightly in syntax and handling of data types (e.g., using long long in C++ to handle potentially large lengths), but the core logic remains consistent. Let's examine a Python example in detail:

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

This code first calculates m as described above. Then, it iterates through the string in reverse (s[::-1]). The modulo operation ensures that k always points to the correct index within the decoded string, even after considering repetitions. The condition k == 0 and c.isalpha() finds the k-th character. Finally, m is adjusted based on whether the current character is a digit or a letter.

The other code examples (Java, C++, Go, TypeScript) implement the same algorithm with minor syntax variations to accommodate their respective languages. The use of BigInts in TypeScript is a precaution to handle potentially very large numbers arising from the repeated string expansion.