# Straightforward O(n) solution in python with detailed explaination

• Lets start by example:

``````S = '1 22 11 2'
S' = '1 2 2 1'
``````

Based on the description we can easily get the next num of S' should be 1 since S' is exactly the substring of S, so the question would become how to compose the next part of S?

The '1' means either 1 or 2 for the next part of S, and the answer must be 1 because if it was 2, then `S = '1 22 11 22'` and S' would be `1 2 2 2`. That's wrong.

So we come up with the conclusion that The next part of S is based on the last num of current S. below is my solution, beat more than 90% python code:

``````class Solution(object):
def magicalString(self, n):
"""
:type n: int
:rtype: int
"""
s, last_s = '122', '2' #initial value, defined formula
ml = 2  #The cout of S'
old = n # Original n
while n > 3:
next_num = s[ml]
if next_num == '2':
if last_s == '2':
s += '11'
last_s = '1'
else:
s += '22'
last_s = '2'
n -=2

if next_num == '1':
if last_s == '1':
s += '2'
last_s = '2'
else:
s += '1'
last_s = '1'
n -= 1
ml += 1
return s[:old].count('1')
``````

Yes, the code may not neat, but how many of you would come up with neat solution on the short interview:)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.