Magical String - Leetcode Solution

The Magical String problem on LeetCode is a bit tricky and requires some understanding of algorithms and data structures. Here is a detailed solution to this problem:

Problem Statement:

A magical string S consists of only '1' and '2' and obeys the following rules:

The string S is magical because every substring of the string that starts with '1' and ends with '2' is itself a magical string (Ex: 12122, 122, 12, 2, etc.).

The first few elements of string S is the following: S = "1221121221221121122……"

If we have an integer N, write a program that will return the number of '1's in the first N number of the magical string S.

Example:

Input: N = 6 Output: 3

Input: N = 10 Output: 4

Solution:

The problem statement tells us that the magical string S can be generated using the following algorithm:

1. Start with the string "122"
2. Find the next character in the string by looking at the last character in the string. If it is '1', add a '2' to the end of the string. If it is '2', add a '1' to the end of the string.
3. Repeat step 2 until the string has length N.

Using this algorithm, we can generate the magical string S and count the number of '1's in the first N characters of the string. Here is the implementation of this algorithm in Python:

class Solution:
    def magicalString(self, n: int) -> int:
        if n == 0:
            return 0
        
        if n <= 3:
            return 1
        
        s = [1, 2, 2]
        p = 2
        count = 1
        
        while len(s) < n:
            num = 3 - s[-1]
            s += [num] * s[p]
            p += 1
            
        for i in range(n):
            if s[i] == 1:
                count += 1
                
        return count

In this implementation, we first handle the base cases where n is 0, 1, 2, or 3. If n is 0, we return 0 because there are no '1's in the string. If n is less than or equal to 3, we return 1 because the first three characters of the string are '1', '2', '2', and there is only one '1' in this substring.

Next, we initialize the string s with the first three characters of the magical string ('1', '2', '2'). We also initialize a pointer p to 2, which is the index of the last character in the first substring ('1', '2') of the string that starts with '1' and ends with '2'. We also initialize a variable count to 1 because the first character of the string is '1', which is counted as a '1'.

We then use a while loop to generate the string s until its length is equal to N. In each iteration of the loop, we first find the next character in the string by looking at the last character in the string. If it is '1', we add a '2' to the end of the string. If it is '2', we add a '1' to the end of the string. We also update the pointer p to point to the index of the last character in the next substring that starts with '1' and ends with '2'.

Finally, we use a for loop to count the number of '1's in the first N characters of the string and return the count.

This implementation has a time complexity of O(N) because we generate the string s and count the number of '1's in it in linear time. The space complexity of this implementation is also O(N) because we store the entire string s in memory.

1