<p>A magical string <code>s</code> consists of only <code>&#39;1&#39;</code> and <code>&#39;2&#39;</code> and obeys the following rules:</p>

<ul>
	<li>The string s is magical because concatenating the number of contiguous occurrences of characters <code>&#39;1&#39;</code> and <code>&#39;2&#39;</code> generates the string <code>s</code> itself.</li>
</ul>

<p>The first few elements of <code>s</code> is <code>s = &quot;1221121221221121122&hellip;&hellip;&quot;</code>. If we group the consecutive <code>1</code>&#39;s and <code>2</code>&#39;s in <code>s</code>, it will be <code>&quot;1 22 11 2 1 22 1 22 11 2 11 22 ......&quot;</code> and the occurrences of <code>1</code>&#39;s or <code>2</code>&#39;s in each group are <code>&quot;1 2 2 1 1 2 1 2 2 1 2 2 ......&quot;</code>. You can see that the occurrence sequence is <code>s</code> itself.</p>

<p>Given an integer <code>n</code>, return the number of <code>1</code>&#39;s in the first <code>n</code> number in the magical string <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 6
<strong>Output:</strong> 3
<strong>Explanation:</strong> The first 6 elements of magical string s is &quot;122112&quot; and it contains three 1&#39;s, so return 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
</ul>

'''
i is the index of the string at which the value (int(s[i])) tells how many TIMES the next number should appear.

How do we know what the next number should be? use the string itself. - whatever the
last char is currently, we need to put the OPPOSITE.  


Why use an array of chars to represemt the string in the solution instead of a string itself?
ChatGPT
Using an array of characters (a list in Python) instead of a string in this solution is more efficient when mutability is needed. Here’s why:

1. Mutability:
Strings are immutable in Python. This means that every time you modify a string (e.g., by concatenating characters), Python creates a new string object.
Lists (arrays) are mutable. You can modify them in place (e.g., by appending or changing elements) without creating a new object each time.
In the magical string problem, the string is built dynamically by repeatedly appending characters. If a string were used instead of a list:

Each time you append a character, a new string would be created.
This would result in poor performance, especially for larger inputs, because Python would have to allocate memory for a new string and copy over the existing characters each time.

'''

class Solution:
    def magicalString(self, n: int) -> int:
        s, i = ["1", "2", "2"], 2 # we represent the string as an array of characters
        while len(s) < n:
            s += (["1"] if s[-1] == '2' else ["2"]) * int(s[i])
            # ex.when s = ["1", "2", "2"] and i = 2,
            # we will add '1' two times to s (twice since s[2] = 2
            # and we end up with  ["1", "2", "2", '1', "1",].
            i += 1
            # and even though we just added 2 chars for this example iteration, we inc i by 1 only

        return s[:n].count('1')



        #                                    i
        # "1", "2", "2", "1", "1", "2", "1", 2, 2, 1, 2, 2
17900