880. Decoded String at Index
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.
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 multiplym
byd
. This is because the character indicates that the sequence before this digit should be repeatedd
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 dividem
byd
to step backwards out of the current repeated segment. - When we encounter a letter, we subtract 1 from
m
. If at this pointk
equals 0 and the current character is a letter, this means we have found thekth
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 encounter2
, so we skip it since we have not encountered any letters yet. - We encounter letters
abc
and incrementm
by 3 (for each letter), som = 3
. - The next digit is
2
, which tells us to multiply the currentm
by2
, som = 3 * 2 = 6
. - We then encounter
3[cd]
. Aftercd
ourm
becomes6 + 2 = 8
and then seeing3
we multiplym
by3
, som = 8 * 3 = 24
. - Finally, we have the letters
ef
which add2
more tom
, making it24 + 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 lettersfe
sincek
is greater than2
. - We then see digit
3
. We divide our total lengthm
by3
, giving usm = 26 / 3 ≈ 8
. Herek
is still greater than8
, so we continue. - We encounter
cd
. Sincek
is9
and we are looking for one character, we dok %= m
, which doesn’t changek
since9 < m
. - The next digit is
2
, we dividem
by2
to getm = 8 / 2 = 4
. Now,k = 9
is greater thanm
, so we dok %= m
and getk = 1
. - We will now encounter the letters
cba
in reverse. Sincek = 1
, once we decrementm
by1
three times (while skipping over letterscba
), we reachk = 0
on the lettera
.
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
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:
- The first
for
loop iterates over each character of the string once, giving a complexity ofO(N)
for this part. - 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 remainsO(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:
- A fixed number of single-value variables are used (
m
andk
). - No additional data structures that grow with the input size are utilized.
- 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.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.