What is a magical string in LeetCode problem 481?

A magical string consists only of '1's and '2's where grouping consecutive identical numbers produces counts that reconstruct the string itself.

How do I efficiently count '1's in the first n characters?

Use a two-pointer approach to generate the string up to n, tracking group sizes and counting '1's as you append each segment.

Can this problem be solved without building the full string?

Yes, you can stream counts using two pointers and maintain only current group values to compute the count of '1's without storing the entire string.

Why is two-pointer scanning important for Magical String?

It ensures the invariant that each group size drives the next segment generation, avoiding off-by-one mistakes and unnecessary full simulations.

What are edge cases to watch for?

Edge cases include n smaller than the initial prefix, consecutive repeats at the end, and correctly alternating numbers while counting '1's.

#481

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

神奇字符串

神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：将连续相同字符组 '1' 和 '2' 长度的序列连接起来会生成字符串 s 本身。 s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中连续的若干 1 和 2 进行分组，可以得到 "1 22…

双指针字符串

题目描述

神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：

将连续相同字符组 '1' 和 '2' 长度的序列连接起来会生成字符串 s 本身。

s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中连续的若干 1 和 2 进行分组，可以得到 "1 22 11 2 1 22 1 22 11 2 11 22 ......" 。每组中 1 或者 2 的出现次数分别是 "1 2 2 1 1 2 1 2 2 1 2 2 ......" 。上面的出现次数正是 s 自身。

给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。

示例 1：

输入：n = 6
输出：3
解释：神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 10⁵

lightbulb

解题思路

方法一：模拟构造过程

根据题目，我们得知，字符串 $s$ 的每一组数字都可以由字符串 $s$ 自身的数字得到。

字符串 $s$ 前两组数字为 $1$ 和 $22$ ，是由字符串 $s$ 的第一个数字 $1$ 和第二个数字 $2$ 得到的，并且第一组数字只包含 $1$ ，第二组数字只包含 $2$ ，第三组数字只包含 $1$ ，以此类推。

由于前两组数字已知，我们初始化字符串 $s$ 为 $122$ ，然后从第三组开始构造，第三组数字是由字符串 $s$ 的第三个数字（下标 $i=2$ ）得到，因此我们此时将指针 $i$ 指向字符串 $s$ 的第三个数字 $2$ 。

1 2 2
    ^
    i

指针 $i$ 指向的数字为 $2$ ，表示第三组的数字会出现两次，并且，由于前一组数字为 $2$ ，组之间数字交替出现，因此第三组数字为两个 $1$ ，即 $11$ 。构造后，指针 $i$ 移动到下一个位置，即指向字符串 $s$ 的第四个数字 $1$ 。

1 2 2 1 1
      ^
      i

这时候指针 $i$ 指向的数字为 $1$ ，表示第四组的数字会出现一次，并且，由于前一组数字为 $1$ ，组之间数字交替出现，因此第四组数字为一个 $2$ ，即 $2$ 。构造后，指针 $i$ 移动到下一个位置，即指向字符串 $s$ 的第五个数字 $1$ 。

1 2 2 1 1 2
        ^
        i

我们按照这个规则，依次模拟构造过程，直到字符串 $s$ 的长度大于等于 $n$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def magicalString(self, n: int) -> int:
        s = [1, 2, 2]
        i = 2
        while len(s) < n:
            pre = s[-1]
            cur = 3 - pre
            # cur 表示这一组的数字，s[i] 表示这一组数字出现的次数
            s += [cur] * s[i]
            i += 1
        return s[:n].count(1)

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is processed once with the two-pointer scan. Space complexity is O(n) for storing the partial magical string and tracking counts, though optimizations may reduce memory by streaming counts without full string storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate recognizes need to generate groups incrementally instead of simulating the infinite string.
question_mark
Candidate sets up two pointers to track group sizes and alternating values correctly.
question_mark
Candidate properly updates '1's count while maintaining invariants and handles edge cases where consecutive numbers repeat.

warning

常见陷阱

外企场景

error
Appending numbers incorrectly without following the alternating pattern leads to wrong counts.
error
Mismanaging the read/write pointers can skip or duplicate groups.
error
Failing to count '1's during generation instead of scanning after full string causes inefficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute number of '2's instead of '1's in the first n characters.
arrow_right_alt
Generate magical string using constant space by streaming counts rather than storing the string.
arrow_right_alt
Modify the problem to return the nth character in the magical string instead of counting occurrences.

help

常见问题

外企场景

继续练习

#443 压缩字符串 #522 最长特殊序列 II #524 通过删除字母匹配到字典里最长单词