Magical String — LeetCode 481 Python Solution

The problem

A magical string s consists of only '1' and '2' and obeys the following rule: Concatenating the sequence of lengths of its consecutive groups of identical characters '1' and '2' generates the string s itself. The first few elements of s is s = "1221121221221121122……".

Example

Input

n = 6

Output

3

Explanation

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

Python solution

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)

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 481. Magical String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems