Here is my observation, this magic string keep generating and appending itself. So I come up with a Deque solution in which the head of the queue serves as generator (1 or 2) while the tail of the queue serves as appending.

However, somehow I notice the initial sequence 122 is a special case:

- The first 2 belongs to a pattern of 22, which is tricky and this is the only place. In future, if encounter a generator as 2, we can always append either double 1s or double 2s.
- This is the only place the Deque may be empty when poll the second 2. In future, the queue will always have more than 2 elements.

So I will start process with 11. And the below code will speak for the rest.

```
public int magicalString(int n) {
if(n==0)
return 0;
if(n<=3)
return 1;
Deque<Integer> dq = new LinkedList<>();
dq.offerFirst(1); dq.offerFirst(1);
n = n-3;
int count = 1;
while(n-->0) {
if(dq.pollFirst()==1) {
count++;
if(dq.peekLast()==1)
dq.offerLast(2);
else
dq.offerLast(1);
} else {
if(dq.peekLast()==1) {
dq.offerLast(2);
dq.offerLast(2);
} else {
dq.offerLast(1);
dq.offerLast(1);
}
}
}
return count;
}
```