Magical String: Self-Describing Sequence Generation

LeetCode 481, Magical String, gives you a string that describes itself. The magical string starts with "1221121221221121122..." and is constructed from only the digits 1 and 2. The twist is that the sequence of group lengths in this string is the string itself.

Here is how it works. The string is made up of groups of consecutive 1s and 2s. If you list the length of each group, you get back the original string:

• Groups: 1, 22, 11, 2, 1, 22, 1, 22, 11, ...
• Lengths: 1, 2, 2, 1, 1, 2, 1, 2, 2, ...
• Which is: 1 2 2 1 1 2 1 2 2 ... (the magical string itself!)

Given an integer n, you need to count how many 1s appear in the first n characters of this string.

The key insight is that you do not need to figure out the whole string up front. You can generate it on the fly by reading from the beginning of the string to decide how long each new group should be.

The approach: generate and count

The plan breaks down into a few pieces:

1. Seed the string with "122". This is the fixed starting point for the magical string.
2. Keep a read pointer (i) that walks through the string from left to right. The value at s[i] tells you how many characters to write in the next group.
3. Keep track of which digit to write next. The groups alternate between 1 and 2 (starting with the third group, which is a group of 1s).
4. Append s[i] copies of the current digit to the string, then flip the digit for the next group and advance the read pointer.
5. Once the string is at least n characters long, count the 1s in the first n characters.

The beauty of this problem is that the string tells you how to build itself. The read pointer chases the write pointer, and the string grows just fast enough to stay ahead.

The code

def magicalString(n):
    if n == 0:
        return 0
    s = [1, 2, 2]
    read = 2
    digit = 1
    while len(s) < n:
        count = s[read]
        s.extend([digit] * count)
        digit = 3 - digit
        read += 1
    return s[:n].count(1)

Walk through what happens:

1. Handle the edge case where n is 0 by returning 0 immediately.
2. Initialize the string as a list [1, 2, 2], which is the fixed seed.
3. Set the read pointer to index 2 (the first position that controls a new group) and the current digit to 1 (the next group to write).
4. While the string is shorter than n, read s[read] to get the group length. Append that many copies of digit to the list.
5. Flip the digit using 3 - digit (this swaps 1 and 2 back and forth). Advance the read pointer.
6. Once the string is long enough, slice the first n elements and count how many are 1.

Visual walkthrough

Here is a step-by-step trace showing how the magical string grows. Watch how the read pointer advances through the string, and each value it reads determines the size of the next group written.

Notice the self-referential nature: the values you read are themselves part of the string you are building. The read pointer never catches the write pointer because each read produces at least one new character.

Complexity analysis

You generate at most n characters (plus a small overshoot), and each step does constant work. The final count is a linear scan of the first n elements.

Building blocks

This problem is built from two reusable techniques that show up in other string and sequence problems.

Self-referential generation

The core technique here is using a sequence's own content to drive its generation. You maintain a read pointer that consumes the sequence from the front while a write pointer appends to the back. This pattern appears whenever a sequence's structure is defined recursively in terms of itself.

Other problems that use this pattern:

• Count and Say (LeetCode 38) generates each term by reading aloud the previous term, which is a similar "read to produce" loop.
• Decode String (LeetCode 394) reads encoded instructions from a string to produce expanded output.

Digit toggling with arithmetic

The trick 3 - digit to swap between 1 and 2 is a clean way to alternate between two values without if-else branches. Any time you need to toggle between two specific values a and b, you can use (a + b) - current. This shows up in problems involving two-state alternation, like coloring or parity tracking.

Edge cases

n = 0. There are zero characters to examine, so the answer is 0. The early return handles this before any generation logic runs.

n = 1. The first character is always 1, so the answer is 1. The seed [1, 2, 2] already covers this without entering the while loop.

n = 2 or n = 3. The seed [1, 2, 2] has length 3, so these cases are covered without generating any new groups. For n = 2, the first two characters are 1, 2, giving one 1. For n = 3, the first three are 1, 2, 2, still one 1.

Large n. The string grows roughly in proportion to n. Each iteration of the while loop adds either 1 or 2 characters, so the loop runs at most n times. There is no risk of infinite loops because the read pointer always advances and always finds a valid value (1 or 2).

From understanding to recall

You can read through this solution and follow every step. But the parts that tend to slip away are the specific ones: seeding with [1, 2, 2], starting the read pointer at index 2 (not 0 or 1), using 3 - digit to toggle, and remembering to slice to exactly n before counting.

Spaced repetition locks these details in. You drill the self-referential generation loop as one brick and the digit-toggling trick as another. Each rep takes a minute or two. After a few rounds at increasing intervals, the seed, the pointer setup, and the toggle pattern become automatic. When you see a self-describing sequence problem in an interview, you are not reinventing the generation logic. You are snapping together bricks you already own.

Related posts

• Count and Say - Another sequence generation problem where each term is produced by reading the previous one
• String Compression - In-place run-length encoding that uses the same group-scanning pattern
• Decode String - Expanding encoded patterns from a string, the reverse direction of compression