Decoded String at Index

Problem Statement

In this task, you are provided with an encoded string s. To decode this string, you follow a specific set of operations where each character is processed in sequence:

• If the character is a letter, it is directly written onto an output tape.
• If the character is a digit d, it instructs to repeat everything that has been written so far on the tape d - 1 additional times.

Given another parameter k which is a 1-indexed position in the decoded tape, your goal is to determine what letter appears at the kth position in the fully decoded string.

Examples

Example 1

Input:

s = "Vul2tr3", k = 7

Output:

"o"

Explanation:

The decoded string is "VuVultrVuVultrVuVultr".
The 7th letter in the string is "r".

Example 2

Input:

s = "ha22", k = 5

Output:

"h"

Explanation:

The decoded string is "hahahaha".
The 5th letter is "h".

Example 3

Input:

s = "a2345678999999999999999", k = 1

Output:

"a"

Explanation:

The decoded string is "a" repeated 8301530446056247680 times.
The 1st letter is "a".

Constraints

• 2 <= s.length <= 100
• s consists of lowercase English letters and digits 2 through 9.
• s starts with a letter.
• 1 <= k <= 109
• It is guaranteed that k is less than or equal to the length of the decoded string.
• The decoded string is guaranteed to have less than 263 letters.

Approach and Intuition

The challenge mainly revolves around efficiently determining the kth character without explicitly constructing the entire decoded string, which can be prohibitively large. Let’s break down the approach with our understanding from the examples:

1. Recognize that a digit d indicates a multiplication of the sequence built so far by d. Hence, after processing each character (or digit), we know the total length of the constructed sequence at that step.

2. Maintain a running length of the decoded string as we process each character. For letters, this length increases by one. For digits, the current length can potentially multiply, resulting in an exponential growth depending on the digit.

3. Given that we only need the kth character:

   • If at any point, our running length exceeds or meets k, we focus on this segment as it contains our desired character.
   • If a digit creates a sequence larger than k, then backtrack to see which part of the sequence preceding the digit corresponds to the kth position.

Using these observations:

• Example 1 ("Vu2ltr3", k = 7):

  • After "Vu2", the sequence becomes "VuVu". The length is now longer than earlier but still less than 10.
  • Adding "ltr" results in "VuVultr".
  • Applying "3" results in "VuVultrVuVultrVuVultr". The 7th character in this sequence is "r".

• Example 2 ("ha22", k = 5):

  • Applying the two '2's after "ha" causes the sequence "ha" to repeat, becoming "hahahaha". The fifth character in this sequence is "h".

• Example 3 ("a2345678999999999999999", k = 1):

  • The digits following 'a' expand the sequence exponentially, but since k=1, it remains the first character "a".

This approach ultimately revolves around using the arithmetic progression to dissect the problem rather than constructing enormous strings, being both time-efficient and memory-friendly. This methodology leverages the understanding of sequential processing and exponential growth induced by the digits.

Solutions

class Solution {
public:
    string solve(string inputStr, int position) {
        long totalLength = 0;
        int length = inputStr.length();
    
        // Calculate total length when the string is fully decoded
        for (int index = 0; index < length; ++index) {
            if (isdigit(inputStr[index]))
                totalLength *= inputStr[index] - '0';
            else
                totalLength++;
        }
    
        for (int index = length - 1; index >= 0; --index) {
            position %= totalLength;
            if (position == 0 && isalpha(inputStr[index]))
                return (string) "" + inputStr[index];
    
            if (isdigit(inputStr[index]))
                totalLength /= inputStr[index] - '0';
            else
                totalLength--;
        }
        return "";
    }
};