algoadvance

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 is a letter, that letter is written onto the tape.
• If the character is a digit (between 2 and 9), the entire current tape is repeatedly written d-1 more times, where d is the digit.

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

Example:

Input: s = "leet2code3", k = 10
Output: "o"

Input: s = "ha22", k = 5
Output: "h"

Constraints:

• 2 <= s.length <= 100
• 1 <= k <= 10^9
• s contains only lowercase English letters and digits 2 through 9.
• It’s guaranteed that k is less than or equal to the length of the decoded string.

Clarifying Questions

1. Is it guaranteed that the encoded string s will be well-formed without any invalid characters?
2. Does the string always contain only lowercase letters and digits 2 through 9?
3. Can k be larger than the length of the string s?

Strategy

1. Reverse Analysis: Instead of decoding the string fully (which is impractical due to potential size), start analyzing the structure in reverse.
2. Identify Loops and Characters: By walking backward from the end of the string:
   • If it’s a digit, adjust the size of the ‘decoded’ part accordingly.
   • If it’s a letter, check if the current size includes the kth position.
3. Calculating Effective Size: Use tracking of the overall size of the decoded string during backward traversal to determine the exact point.
4. Modulo Operation: Utilize modular arithmetic to effectively reduce k as decoding progresses backward.

Code

def decodeAtIndex(s: str, k: int) -> str:
    size = 0
    # Find size 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

# Example usage
print(decodeAtIndex("leet2code3", 10))  # Output: "o"
print(decodeAtIndex("ha22", 5))  # Output: "h"

Explanation

1. Initialize size to 0: This keeps track of the size of the decoded string.
2. Calculate Decoded Size:
   • Traverse s and update size. For digits, multiply size by the digit value.
   • For letters, increment size by one.
3. Traverse in Reverse:
   • By reducing k using modular arithmetic (k % size), shrink the problem size.
   • When encountering a letter check if it’s the kth position.
   • Adjust size backward for both digits and letters.
4. Returning Result: When k == 0 for a letter, it means the current letter is the result.

Time Complexity

The time complexity is (O(n)), where (n) is the length of the string s, since we’re traversing the string a couple of times. This is efficient given the constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?