Decoded String at Index

Problem Description

You are given an encoded string s. To decode the 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 d, the entire current tape is repeatedly written d - 1 more times in total.

Given an integer k, return the kth letter (1-indexed) in the decoded string.

Key Insights

• The decoded string can grow exponentially due to digits in the input string.
• Direct decoding of the entire string is inefficient, particularly when k can be as large as 10^9.
• Instead of building the entire decoded string, we can calculate the effective length of the tape as we parse the string from the end to the beginning.
• By tracking the lengths and using division/modulus, we can determine the position of the kth character efficiently.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s (since we process each character once). Space Complexity: O(1), as we only need a constant amount of space for variables.

Solution

To solve the problem, we will:

1. Iterate through the string s from the end to the beginning.
2. Maintain a variable length to track the current length of the decoded string.
3. For each character:
   • If it's a letter, check if the current length is equal to or greater than k. If so, we have found our character.
   • If it's a digit, multiply the length by this digit.
4. Continue this process until we locate the kth character.

The primary data structure used here is a simple integer to keep track of the length.

Code Solutions