We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decoded String at Index

Number: 916

Difficulty: Medium

Paid? No

Companies: PhonePe, Amazon, National Instruments

Problem Description

Given an encoded string that contains lowercase letters and digits (2-9), where digits indicate that the current tape (decoded string so far) should be repeated, find the kth letter (1-indexed) in the fully decoded string without actually decoding the entire string.

Key Insights

  • Directly decoding the string is infeasible due to potential enormous sizes.
  • Calculate the length of the decoded string using a forward pass.
  • Use a reverse engineering approach: work backwards through the encoded string and apply modulo arithmetic to determine which letter the kth position corresponds to.
  • When encountering a digit, divide the current length by that digit.
  • When encountering a letter, if k equals the current length (or after appropriate modulo), that letter is the answer.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the encoded string (n ≤ 100). Space Complexity: O(1) additional space (only a few variables used).

Solution

The solution involves two main passes:

  1. A forward pass to compute the total length of the decoded string without constructing it.
  2. A backward pass to find the kth character by reverse simulating the decoding process:
    • If a digit is encountered during the reverse pass, update k using modulo arithmetic since the sequence is repeated.
    • If a letter is encountered, check if it is the kth letter or reduce the length count appropriately. This reverse simulation effectively “peels off” layers of repetition introduced by digits until we directly identify the character.

Code Solutions

# Python solution with line-by-line comments

def decodeAtIndex(s: str, k: int) -> str:
    # Calculate total length of decoded string without actual decoding
    decoded_length = 0
    for char in s:
        if char.isdigit():
            # Multiply current length by digit
            decoded_length *= int(char)
        else:
            # Increment length for a letter
            decoded_length += 1

    # Process the encoded string in reverse order to find kth character
    for char in reversed(s):
        # Mod k with the current decoded_length to handle cyclical repetition
        k %= decoded_length
        if k == 0 and char.isalpha():
            # If k is 0, we found the letter that starts the repeated segment
            return char
        if char.isdigit():
            # If char is a digit, divide the decoded_length
            decoded_length //= int(char)
        else:
            # If char is a letter, simply reduce the decoded_length by 1
            decoded_length -= 1

# Example usage:
# print(decodeAtIndex("leet2code3", 10))
← Back to All Questions