880. Decoded String at Index

MediumStackString
Leetcode Link

Problem Description

You are tasked with deciphering an encoded string s. The encoding process operates under two simple rules. If you encounter a letter during the decoding process, you simply write it down. However, if you run into a digit d, then you need to replicate the entire decoded string (up until that point), d - 1 additional times.

Now, with this encoded string, you're given a task to find out the kth letter in the resultant decoded string where k is 1-indexed. The challenge lies in the fact that the decoded string can potentially become very large, and thus, it may not be feasible to decode the entire string just to find one character.

Intuition

The solution approach is built upon a key observation to avoid decoding the entire string, which could consume a lot of time and space, particularly if the string is very large.

To begin with, we figure out the full length of the decoded string without actually decoding it. This is possible by iterating over the encoded string and applying the rules: we increment our length by 1 for a letter, and we multiply our current length by d when we encounter a digit.

Once we have the total length, we then think in reverse: starting from the end of the encoded string, we work backwards given that the structure of the encoded string is inherently repetitive and redundant due to the digits. By doing modulus k % m at each step (where m is the length at that point), we are effectively peeling off the outer layers of this repetitive structure, reducing k to find the position in the smaller version of the string.

When we come across a digit while iterating backwards, it tells us that the current string is a repetition caused by this digit, so we divide m by the digit to step into the inner layer of the next repetition, undoing the previous expansion. If the character is a letter and k becomes 0, it means we have successfully reversed into the original non-repeated string with the correct position, and we can thus return this character.

The trick here is recognizing that instead of expanding the encoded string, we shrink k until we can directly map it to the correct character. By reversing the process (both the string and the decoding steps), we significantly optimize for both time and space.

Learn more about Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used in a depth first search?

Solution Approach

The implementation follows a two-pass approach:

In the first pass, we traverse the encoded string s from start to end to calculate the total length m of the decoded string. This is done by iterating through each character in the string:

  • If the character is a letter, we increment m by 1, because each letter adds a single character to the decoded string.
  • If the character is a digit d, we multiply m by d. This is because the character indicates that the sequence before this digit should be repeated d times.

After the first pass, we have the total length m without having to store the decoded string.

In the second pass, we reverse iterate the string (hence the use of s[::-1]) and decrement k modulo m. The modulo operation effectively reduces the size of k to fit within the current size of the non-repeated string.

During this reverse iteration:

  • Each time we encounter a digit d, it indicates the start of a multiplied segment. Therefore, we divide m by d to step backwards out of the current repeated segment.
  • When we encounter a letter, we subtract 1 from m. If at this point k equals 0 and the current character is a letter, this means we have found the kth character in the decoded string.

The use of modulo operation (k %= m) is particularly crucial as it keeps shrinking k to stay within the bounds of the "virtual" decoded string we are constructing.

This approach avoids the need to construct the entire decoded string, which is critical for memory efficiency, especially when the size of the decoded string is enormous. It is an excellent example of space optimization, where the understanding of the problem's constraints (such as the predictable repetitiveness of the encoded string) is leveraged to eliminate unnecessary work.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let’s go through an example to illustrate the solution approach.

Consider the encoded string s = "2[abc]3[cd]ef", and we want to determine the 9th letter in the decoded string.

In the first pass, we would calculate the full length m of the decoded string as follows:

  • We start with m = 0 and we encounter 2, so we skip it since we have not encountered any letters yet.
  • We encounter letters abc and increment m by 3 (for each letter), so m = 3.
  • The next digit is 2, which tells us to multiply the current m by 2, so m = 3 * 2 = 6.
  • We then encounter 3[cd]. After cd our m becomes 6 + 2 = 8 and then seeing 3 we multiply m by 3, so m = 8 * 3 = 24.
  • Finally, we have the letters ef which add 2 more to m, making it 24 + 2 = 26.

So, without decoding, we know the length m of the decoded string would be 26.

In the second pass, we work backwards to find the 9th letter:

  • We start with k = 9. Going in reverse, we skip the first two letters fe since k is greater than 2.
  • We then see digit 3. We divide our total length m by 3, giving us m = 26 / 3 ≈ 8. Here k is still greater than 8, so we continue.
  • We encounter cd. Since k is 9 and we are looking for one character, we do k %= m, which doesn’t change k since 9 < m.
  • The next digit is 2, we divide m by 2 to get m = 8 / 2 = 4. Now, k = 9 is greater than m, so we do k %= m and get k = 1.
  • We will now encounter the letters cba in reverse. Since k = 1, once we decrement m by 1 three times (while skipping over letters cba), we reach k = 0 on the letter a.

Once k becomes 0, the current character, a, is the 9th letter in the decoded string. Note that we did not need to decode the entire string, which saves a significant amount of time and space. This strategy is particularly effective as the strings grow in length and complexity.

Solution Implementation

1class Solution:
2    def decodeAtIndex(self, tape: str, k: int) -> str:
3        size = 0  # This will represent the size of the decoded string
4      
5        # Calculate size of the decoded string
6        for char in tape:
7            if char.isdigit():
8                size *= int(char)  # If character is a digit, multiply the size
9            else:
10                size += 1  # If character is a letter, increment the size
11
12        # Iterate over the string in reverse to find the k-th character
13        for char in reversed(tape):
14            k %= size  # k could be larger than size, ensure we cycle within bounds of 'size'
15            if k == 0 and char.isalpha():
16                return char  # If k is 0 and char is a letter, this is the answer
17          
18            # If character is a digit, divide the size,
19            # else if character is a letter, decrease size
20            if char.isdigit():
21                size //= int(char)  # Divide the size by the digit
22            else:
23                size -= 1  # Decrease the size for the letter
24
25# Sample usage:
26sol = Solution()
27result = sol.decodeAtIndex("leet2code3", 10)
28print(result)  # Should print the 10th character in the decoded string
29
1class Solution {
2
3    // Decodes a string at the specified index 'k'
4    public String decodeAtIndex(String S, int K) {
5        long size = 0; // This will hold the size of the decoded string until a given point
6      
7        // First pass: Calculate the size of the decoded string
8        for (int i = 0; i < S.length(); ++i) {
9            char c = S.charAt(i);
10            if (Character.isDigit(c)) {
11                // If it's a digit, multiply the current size by the digit to simulate the repeat-expansion
12                size *= c - '0';
13            } else {
14                // If it's a letter, increment the size
15                ++size;
16            }
17        }
18      
19        // Second pass: Work backwards to find the k-th character
20        for (int i = S.length() - 1; ; --i) {
21            K %= size; // Modulate K with current size to handle wrap around cases
22            char c = S.charAt(i);
23          
24            if (K == 0 && !Character.isDigit(c)) {
25                // If K is zero, and we're at a character, that's the character we want to return
26                return String.valueOf(c);
27            }
28          
29            if (Character.isDigit(c)) {
30                // If it's a digit, we reverse the expansion by dividing the size
31                size /= c - '0';
32            } else {
33                // If it's an alphabet character, decrement the size as we move left
34                --size;
35            }
36        }
37    }
38}
39
1#include <string>
2#include <cctype> // for isdigit and isalpha functions
3
4class Solution {
5public:
6    /**
7     * Decodes the string at the specified index.
8     * 
9     * Each letter (lowercase and uppercase) in the string will be written to a tape. 
10     * For each number in the string, the entire current tape is repeated that number of times. 
11     * Given a string that has been encoded in this way and an index k, return the k-th letter (1-indexed).
12     * 
13     * @param s The encoded string consisting of lowercase letters, uppercase letters, and digits.
14     * @param k The 1-indexed position in the decoded string.
15     * @return A single character string representing the k-th letter in the decoded string.
16     */
17    string decodeAtIndex(string s, int k) {
18        // Using a long long to handle the possible length of the decoded string.
19        long long decodedLength = 0;
20
21        // First pass to calculate the length of the decoded string.
22        for (const char& c : s) {
23            if (isdigit(c)) {
24                decodedLength *= (c - '0'); // Multiplies the current length by the digit.
25            } else {
26                ++decodedLength; // Increment the length for a character.
27            }
28        }
29
30        // Reverse iteration over the encoded string.
31        for (int i = s.size() - 1; i >= 0; --i) {
32            // Modulo operation to find the effective index.
33            k %= decodedLength;
34            // If k is 0 and character is an alphabet, return this character.
35            if (k == 0 && isalpha(s[i])) {
36                return string(1, s[i]);
37            }
38            // If current character is a digit, divide decodedLength by the digit.
39            // This effectively reverses the encoding process.
40            if (isdigit(s[i])) {
41                decodedLength /= (s[i] - '0');
42            } else {
43                // If it's an alphabet decrement the length count.
44                --decodedLength;
45            }
46        }
47
48        // Given the problem constraints, we should never reach this point.
49        // This is here to satisfy the compiler warning of reaching end of non-void function.
50        return "";
51    }
52};
53
1function decodeAtIndex(S: string, K: number): string {
2    // `decodedSize` represents the length of the decoded string.
3    let decodedSize = 0n;
4  
5    // Calculate the length of the fully expanded string without actual expansion.
6    for (const char of S) {
7        if (char >= '2' && char <= '9') {
8            decodedSize *= BigInt(char);
9        } else {
10            ++decodedSize;
11        }
12    }
13  
14    // Starting from the end, try to find the character at the K-th position.
15    for (let i = S.length - 1; i >= 0; --i) {
16        // Adjust K to be within the bounds of the current pattern.
17        K %= Number(decodedSize);
18      
19        // If K is 0 or matches the current character, return this character.
20        if (K === 0 && S[i] >= 'a' && S[i] <= 'z') {
21            return S[i];
22        }
23      
24        // If the character is a digit, shrink the decoded size accordingly.
25        if (S[i] >= '2' && S[i] <= '9') {
26            decodedSize /= BigInt(S[i]);
27        } else {
28            // If the character is a letter, reduce the size as we move past the character.
29            --decodedSize;
30        }
31    }
32  
33    // The function should never reach this point because the loops should return a value.
34    // However, TypeScript requires a return at the end, so we throw an error to indicate abnormal behaviour.
35    throw new Error('No character found at the given index');
36}
37
Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(N), where N is the length of the input string s. The reasoning behind this is as follows:

  1. The first for loop iterates over each character of the string once, giving a complexity of O(N) for this part.
  2. The second for loop also iterates over each character of the string once, but in reverse order, which does not change the complexity, thus it remains O(N) for this part.

Combining both loops that sequentially iterate over the string without any nested iterations leads to an overall time complexity of O(N).

Space Complexity

The space complexity of the code is O(1). This is because:

  1. A fixed number of single-value variables are used (m and k).
  2. No additional data structures that grow with the input size are utilized.
  3. The for loop utilizes reverse iteration (s[::-1]) which in Python does create a new reversed string, but since the string is not stored and is only used for iteration, the memory remains constant.

In conclusion, the space complexity is unaffected by the size of the input string, and additional memory usage does not scale with N, hence O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫