Length Calculation Without Building the Full String

Sometimes the final string is enormous but its length follows a simple recurrence—compute the length with math or recursion without materializing the string (common in “nth digit of repeated expansion” problems).

Why this shows up in the real world

Fractal L-systems describe plant shapes; simulators query length at depth without drawing every segment. Run-length decoders estimate output size before allocating buffers.

Core idea (explained for students)

Pattern: define f(k) length after k expansions; use doubling or recursion with memoization. When asked for character at position p, recurse choosing left vs right branch based on cumulative lengths.

Try this in Python

def repeat_len(base: str, times: int) -> int:
    return len(base) * times


def digit_at_repeated(s: str, k: int, index: int) -> str:
    # conceptual: expand s k times; return char at index (assume index valid)
    L = len(s) * k
    if index < 0 or index >= L:
        raise IndexError
    return s[index % len(s)]


print(digit_at_repeated("abc", 10**6, 7))

Common mistakes

• Integer overflow in lengths—use Python ints or modulo if problem asks digit only.
• Forgetting base case when recursion bottoms out at single character.

Key takeaways

• Think tree of expansions even if you never build strings—only subtree sizes matter.
• Binary lifting / doubling accelerates deep indices.