#481

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Magical String

Count the number of '1's in the first n characters of a magical string using two-pointer scanning and invariant tracking.

two pointers string

Problem Statement

A magical string s contains only '1' and '2' and is defined recursively: group consecutive identical numbers and the length of each group forms the string itself. For example, the initial sequence begins as s = "1221121221221121122…" where grouping yields counts "1 22 11 2 1 22 1 22 11 2 11 22…" matching the string itself.

Given an integer n, determine how many times '1' appears in the first n characters of this magical string. Constraints are 1 <= n <= 10^5. The goal is to compute this count efficiently using a two-pointer scanning approach that tracks group size and current value without building the entire infinite string. Example: n = 6 returns 3 because the first 6 characters are "122112" containing three '1's.

Examples

Example 1

Input: n = 6

Output: 3

The first 6 elements of magical string s is "122112" and it contains three 1's, so return 3.

Example 2

Input: n = 1

Output: 1

Example details omitted.

Constraints

1 <= n <= 105

Solution Approach

Initialize pointers and string container

Use a dynamic array or string builder to store the magical string. Start with the known prefix "122". Maintain two pointers: one for reading the group size and one for writing the next values.

Iteratively generate the string using two-pointer scanning

At each step, read the count from the read pointer, append that many alternating numbers to the string, and increment the count of '1's when encountered. Move both pointers accordingly. This preserves the invariant that the read pointer always indicates the next group size.

Terminate when reaching n characters and return the result

Stop extending the string once it reaches length n. Return the total count of '1's tracked during generation. This avoids over-computation and ensures linear time relative to n, while space is proportional to n.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Simulate the Construction Process

According to the problem, we know that each group of numbers in the string $s$ can be obtained from the digits of the string $s$ itself.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def magicalString(self, n: int) -> int:
        s = [1, 2, 2]
        i = 2
        while len(s) < n:
            pre = s[-1]
            cur = 3 - pre
            s += [cur] * s[i]
            i += 1
        return s[:n].count(1)

Continue Practicing

#443 string compression #522 longest uncommon subsequence ii #524 longest word in dictionary through deleting