LeetCode 880 - Decoded String at Index

The problem gives us an encoded string s that represents a potentially enormous decoded string. The decoding process works incrementally from left to right. When we encounter a letter, we append it directly to the decoded tape.

leetcodemediumstringstack

LeetCode Problem 880

Difficulty: 🟡 Medium
Topics: String, Stack

Solution

Problem Understanding

The problem gives us an encoded string s that represents a potentially enormous decoded string. The decoding process works incrementally from left to right.

When we encounter a letter, we append it directly to the decoded tape. When we encounter a digit d, we repeat the entire current decoded tape d times in total. In other words, the existing tape is copied d - 1 additional times.

The task is not to fully decode the string. Instead, we only need to determine the character located at position k in the fully decoded string, where indexing is 1-based.

For example, consider:

s = "leet2code3"

The decoding process becomes:

"leet"
"leetleet"
"leetleetcode"
"leetleetcodeleetleetcodeleetleetcode"

The 10th character is "o".

The most important constraint is that the decoded string can become astronomically large. The problem guarantees that the decoded length is less than 2^63, which means it can still be far too large to construct explicitly in memory. Even though the input string length is at most 100, repeated multiplications by digits can create decoded strings with trillions or quintillions of characters.

This immediately tells us that any approach that actually builds the decoded string is infeasible.

Several edge cases are important:

  • A single character may be expanded many times through repeated multiplications.
  • The answer may lie deep inside repeated sections.
  • k may point to a position that corresponds to an earlier prefix before expansion.
  • The decoded length can exceed standard 32-bit integer ranges, so implementations must carefully handle large numbers.
  • The string always starts with a letter, which simplifies initialization logic.
  • The problem guarantees that k is always valid within the decoded string length.

Approaches

Brute Force Approach

The most straightforward solution is to literally decode the string.

We iterate through s character by character. If the character is a letter, we append it to a growing decoded string. If the character is a digit d, we repeat the current decoded string d times.

Once the decoded string is built, we simply return the character at index k - 1.

This approach is correct because it directly simulates the decoding rules exactly as described in the problem statement.

However, it is completely impractical for the given constraints. The decoded string may contain up to nearly 2^63 characters. Constructing such a string would require impossible amounts of memory and time.

Optimal Approach

The key insight is that we never actually need the decoded string itself. We only need to know which original character contributes to the kth position.

Instead of decoding forward, we track only the length of the decoded string as we process characters.

Suppose the decoded length becomes size.

  • If we see a letter, the size increases by 1.
  • If we see a digit d, the entire current string is repeated d times, so the size becomes size * d.

After computing the final decoded length, we work backward through the encoded string.

This reverse traversal is the crucial observation.

When moving backward:

  • If we encounter a digit d, it means the current decoded string was formed by repeating an earlier string d times.
  • Therefore, position k inside the repeated string corresponds to:
k % previous_size

This effectively "rewinds" the expansion.

If we encounter a letter and k points exactly to that position, we have found the answer.

This approach avoids constructing the decoded string entirely and works in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(decoded_length) O(decoded_length) Explicitly builds the full decoded string
Optimal O(n) O(1) Tracks lengths and works backward without decoding

Algorithm Walkthrough

  1. Initialize a variable decoded_length to 0.

This variable represents the length of the decoded string at the current point in processing. 2. Traverse the encoded string from left to right.

For each character:

  • If it is a letter, increment decoded_length by 1.
  • If it is a digit d, multiply decoded_length by d.

After this pass, decoded_length equals the total length of the fully decoded string. 3. Traverse the encoded string again, this time from right to left.

We now work backward to determine which original character maps to position k. 4. At each step, reduce k using modulo arithmetic.

Compute:

k = k % decoded_length

This step is critical because repeated sections wrap around. If the decoded string consists of repeated copies, position k inside the repeated block corresponds to an equivalent position inside the original block. 5. If the current character is a letter, check whether it is the answer.

If either:

k == 0

or

k == decoded_length

then the current letter is exactly the character we are searching for. 6. If the current character is a digit d, divide decoded_length by d.

This reverses the expansion operation and restores the size before repetition. 7. If the current character is a letter and it was not the answer, decrement decoded_length by 1.

This reverses the effect of adding that letter during forward processing. 8. Continue until the answer is found.

Why it works

The algorithm relies on the fact that repetition creates cyclic structure. When a string of length L is repeated d times, any position inside the expanded string corresponds to a position inside the original string modulo L.

By traversing backward and repeatedly shrinking the decoded length, we map the target index k back through every expansion until it corresponds to a concrete letter in the original encoding. Since every reverse step exactly undoes one forward decoding step, the mapping remains correct throughout the process.

Python Solution

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        decoded_length = 0

        # Compute total decoded length
        for char in s:
            if char.isdigit():
                decoded_length *= int(char)
            else:
                decoded_length += 1

        # Work backward to find the kth character
        for char in reversed(s):
            k %= decoded_length

            if k == 0 and char.isalpha():
                return char

            if char.isdigit():
                decoded_length //= int(char)
            else:
                decoded_length -= 1

        return ""

The implementation follows the exact logic described in the algorithm walkthrough.

The first loop computes the total decoded length without constructing the actual decoded string. Letters increase the size by one, while digits multiply the current size.

The second loop processes the string in reverse order. At each iteration, k %= decoded_length maps the current index into the appropriate position within the previous unexpanded section.

When a letter is encountered and k == 0, that letter must be the answer because the modulo operation has narrowed the search down to that exact position.

If the current character is a digit, we reverse the expansion by dividing the decoded length. If the current character is a letter, we reverse the earlier increment by subtracting one.

The algorithm terminates as soon as the correct letter is identified.

Go Solution

func decodeAtIndex(s string, k int) string {
    decodedLength := 0

    // Compute total decoded length
    for _, ch := range s {
        if ch >= '0' && ch <= '9' {
            decodedLength *= int(ch - '0')
        } else {
            decodedLength++
        }
    }

    // Work backward
    for i := len(s) - 1; i >= 0; i-- {
        ch := s[i]

        k %= decodedLength

        if k == 0 && (ch >= 'a' && ch <= 'z') {
            return string(ch)
        }

        if ch >= '0' && ch <= '9' {
            decodedLength /= int(ch - '0')
        } else {
            decodedLength--
        }
    }

    return ""
}

The Go implementation closely mirrors the Python version, but there are a few language-specific considerations.

Go does not provide built-in isdigit or isalpha methods for bytes, so character ranges are checked manually using ASCII comparisons.

The string is traversed backward using indices because Go strings are byte slices. Since the input contains only lowercase English letters and digits, byte indexing is safe and efficient.

Integer arithmetic uses Go's int type. The problem guarantees the decoded length fits within 2^63, so this works correctly on modern 64-bit systems typically used by LeetCode.

Worked Examples

Example 1

s = "leet2code3"
k = 10

Forward Pass

Character Action Decoded Length
l +1 1
e +1 2
e +1 3
t +1 4
2 *2 8
c +1 9
o +1 10
d +1 11
e +1 12
3 *3 36

Backward Pass

Character Current Length k Before Mod k After Mod Result
3 36 10 10 divide by 3 → 12
e 12 10 10 continue
d 11 10 10 continue
o 10 10 0 answer = "o"

Final answer:

"o"

Example 2

s = "ha22"
k = 5

Forward Pass

Character Action Decoded Length
h +1 1
a +1 2
2 *2 4
2 *2 8

Decoded string:

"hahahaha"

Backward Pass

Character Current Length k Before Mod k After Mod Result
2 8 5 5 divide → 4
2 4 5 1 divide → 2
a 2 1 1 continue
h 1 1 0 answer

Final answer:

"h"

Example 3

s = "a2345678999999999999999"
k = 1

Forward Pass

The decoded length grows extremely large through repeated multiplication, but the first character always remains "a".

Backward Pass

Because k = 1, repeated modulo operations keep mapping the target position back to the first character.

Eventually:

Character Current Length k After Mod
a 1 0

Final answer:

"a"

Complexity Analysis

Measure Complexity Explanation
Time O(n) One forward pass and one backward pass through the string
Space O(1) Only a few integer variables are used

The algorithm processes the encoded string twice, once to compute the decoded length and once to trace backward to the target character. Since the input length is at most 100, this is extremely efficient.

No auxiliary data structures proportional to input size are required, so the space usage remains constant.

Test Cases

solution = Solution()

# Provided examples
assert solution.decodeAtIndex("leet2code3", 10) == "o"  # standard example
assert solution.decodeAtIndex("ha22", 5) == "h"  # repeated doubling
assert solution.decodeAtIndex("a2345678999999999999999", 1) == "a"  # huge expansion

# Small basic cases
assert solution.decodeAtIndex("a2", 1) == "a"  # first position
assert solution.decodeAtIndex("a2", 2) == "a"  # repeated character

# Simple repetition
assert solution.decodeAtIndex("abc3", 7) == "a"  # wraps into repeated block
assert solution.decodeAtIndex("abc3", 8) == "b"  # second character in repeat

# Multiple nested expansions
assert solution.decodeAtIndex("ab2c3", 9) == "a"  # nested repetition mapping

# Large k value
assert solution.decodeAtIndex("vk6u5xhq9v", 554) == "k"  # large decoded size

# Single repeated prefix
assert solution.decodeAtIndex("x2y2", 5) == "x"  # repeated prefix interaction

# Edge positions
assert solution.decodeAtIndex("abc2", 1) == "a"  # first character
assert solution.decodeAtIndex("abc2", 6) == "c"  # last character

print("All test cases passed!")
Test Why
"leet2code3", 10 Standard mixed expansion example
"ha22", 5 Multiple sequential multipliers
"a2345678999999999999999", 1 Extremely large decoded length
"a2", 1 Smallest meaningful input
"a2", 2 Repeated single character
"abc3", 7 Modulo wraparound behavior
"abc3", 8 Correct repeated indexing
"ab2c3", 9 Nested expansion correctness
"vk6u5xhq9v", 554 Large index stress test
"x2y2", 5 Interleaved letters and repeats
"abc2", 1 First position boundary
"abc2", 6 Last position boundary

Edge Cases

One important edge case occurs when the decoded string becomes extremely large. A naive solution that constructs the string would quickly run out of memory or time. For example, "a2345678999999999999999" expands to an astronomically large size. The optimal solution avoids this completely by storing only the decoded length rather than the actual string.

Another subtle edge case happens when k lands exactly at the boundary of a repeated block. During backward traversal, the algorithm uses:

k %= decoded_length

If the result becomes 0, it means the target character corresponds to the final character of the current prefix. Many incorrect implementations mishandle this situation and produce off-by-one errors. The condition:

if k == 0 and char.isalpha():

correctly identifies this case.

A third important edge case involves repeated nesting of multipliers. Consider a string like "ha22". The decoded string is expanded multiple times from previously expanded content. A forward decoding simulation would repeatedly duplicate large strings. The reverse traversal handles this naturally because each digit simply reduces the problem size through division and modulo operations.

Another potential source of bugs is integer overflow. The decoded length can exceed standard 32-bit integer ranges. Both implementations use integer types capable of handling large values safely under the problem constraints.