Decoded String at Index

Medium

Asked by:

111 views

Topics:

Strings

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 k^th letter (1-indexed) in the decoded string.

Example 1:

Input: s = "leet2code3", k = 10
Output: "o"
Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10^th letter in the string is "o".

Example 2:

Input: s = "ha22", k = 5
Output: "h"
Explanation: The decoded string is "hahahaha".
The 5^th letter is "h".

Example 3:

Input: s = "a2345678999999999999999", k = 1
Output: "a"
Explanation: The decoded string is "a" repeated 8301530446056247680 times.
The 1^st 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 <= 10⁹
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 2⁶³ letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The encoded string `s` consists of letters and digits. How large can the length of `s` be?
The target index `k` is guaranteed to be within the bounds of the fully decoded string. How large can `k` be? Is it possible for `k` to be 0?
Can the digits in the encoded string be greater than 9, or are they single-digit numbers only?
Does the encoded string always contain at least one letter, or could it consist only of digits? What should I return in the case of an empty decoded string (e.g., s = "2", k = 0)?
Can I assume that the decoded string will fit into memory, or might I need to avoid fully constructing it?

Brute Force Solution

Approach

The problem involves decoding a string that is encoded with repeating substrings. The brute force approach involves fully expanding the encoded string to its decoded form and then directly accessing the character at the target index.

Here's how the algorithm would work step-by-step:

Take the encoded string and start building the fully decoded string.
Go through each part of the encoded string one by one.
If you encounter a letter, add it to the decoded string.
If you encounter a number, this means the preceding substring needs to be repeated that many times.
Repeatedly append the preceding substring to the decoded string the specified number of times.
Continue this process until the entire encoded string has been processed and the decoded string is complete.
Once you have the full decoded string, simply find the character at the desired position (index).

Code Implementation

def decode_string_at_index_brute_force(encoded_string, target_index):    decoded_string = ""
    for character in encoded_string:
        if character.isalpha():
            decoded_string += character
        else:
            # If a digit is found, repeat the previous substring

            repeat_count = int(character)
            last_substring = ""
            
            string_length = len(decoded_string)
            for string_index in range(string_length):
                last_substring += decoded_string[string_index]
            
            original_decoded_string_length = len(decoded_string)
            for _ in range(repeat_count - 1):
                decoded_string += last_substring

    # After decoding, return the character at the target index

    return decoded_string[target_index]

Big(O) Analysis

Time Complexity

O(K*R) – The brute force approach iterates through the encoded string of length n, building the fully decoded string. If a character is encountered, it's appended, which is O(1). If a digit 'R' is encountered, the preceding substring of length 'K' is repeated R times, appending it to the decoded string. The cost of appending this substring repeatedly is K*R. In the worst-case scenario, the entire string consists of a short substring repeated by a large number, leading to a complexity proportional to K*R, where K is the length of the repeated substring and R is the repetition factor.

Space Complexity

O(K) – The provided solution builds the fully decoded string. The length of the decoded string can potentially be very large. Let K represent the length of this fully decoded string. The algorithm requires storing this decoded string in memory as it's built. Therefore, the space complexity is directly proportional to the length of the decoded string K. Thus the auxiliary space used is O(K).

Optimal Solution

Approach

The goal is to find a single character in a very long, potentially repeated string. Instead of fully constructing the decoded string, which would be too slow, we work backwards to figure out where the character at the target position originated from in the original encoded string. This avoids dealing with the entire long string at any point.

Here's how the algorithm would work step-by-step:

Begin by calculating the length of the fully decoded string without actually building it.
Start from the end of the encoded string and move backwards.
Keep track of the current decoded string length.
If you encounter a digit, it means a substring is being repeated. Divide the current decoded length by the digit. Reduce target index using the modulo operation.
If you encounter a letter, check if the current length matches the target index. If it does, return the letter. Otherwise, decrease the current length.
Repeat the process until you find the character at the specified target index.

Code Implementation

def decoded_string_at_index(encoded_string, target_index):    decoded_length = 0
    for char in encoded_string:
        if char.isdigit():
            decoded_length *= int(char)
        else:
            decoded_length += 1

    for i in range(len(encoded_string) - 1, -1, -1):
        char = encoded_string[i]
        if char.isdigit():
            digit = int(char)
            decoded_length //= digit

            # Reduce target index using the modulo operator.
            target_index %= decoded_length

        else:

            # Check if current length matches the target.
            if decoded_length == target_index or (target_index == 0 and decoded_length >= 1):
                return char
            decoded_length -= 1

    return ""

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the encoded string once, from the end to the beginning. In each iteration, it performs a constant amount of work: calculating modulo, comparing the length to the target index, and decrementing the length. The number of iterations is directly proportional to the length (n) of the encoded string (input). Therefore, the time complexity is O(n).

Space Complexity

O(1) – The described algorithm primarily uses a few variables to store the current decoded length and the target index as it iterates backward through the encoded string. It does not create any auxiliary data structures that scale with the input size, such as lists, hash maps, or recursion stacks. The space used by these variables remains constant regardless of the length of the encoded string, which we can denote as N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string S	Return empty string immediately as there is no decoded string at any index.
Index K is 0	If K is 0, there is no character, but depending on the interpretation, return '' or handle it as an invalid input.
String S contains only digits	Repeated string will quickly become very large; handle with modulo and length reduction from end.
String S contains only characters	Simple string traversal and return character at index K if K < length(S).
Large index K exceeding possible string length	Use modulo operation to reduce K relative to the dynamically computed length before decoding.
Integer overflow when calculating decoded string length	Use long data type to prevent integer overflow when calculating decoded string length, before applying the modulo operator.
S contains multiple repeating sections such as a2b3c2	Reduce index K from the end, factoring in each section's repetition count and length.
Maximum-sized string and maximum-sized index	Optimize length calculation and index reduction to avoid timeouts due to extremely large values by applying modulo progressively.

Empty string S

How to Handle:

Return empty string immediately as there is no decoded string at any index.

Index K is 0

How to Handle:

If K is 0, there is no character, but depending on the interpretation, return '' or handle it as an invalid input.

String S contains only digits

How to Handle:

Repeated string will quickly become very large; handle with modulo and length reduction from end.

String S contains only characters

How to Handle:

Simple string traversal and return character at index K if K < length(S).

Large index K exceeding possible string length

How to Handle:

Use modulo operation to reduce K relative to the dynamically computed length before decoding.

Integer overflow when calculating decoded string length

How to Handle:

Use long data type to prevent integer overflow when calculating decoded string length, before applying the modulo operator.

S contains multiple repeating sections such as a2b3c2

How to Handle:

Reduce index K from the end, factoring in each section's repetition count and length.

Maximum-sized string and maximum-sized index

How to Handle:

Optimize length calculation and index reduction to avoid timeouts due to extremely large values by applying modulo progressively.