Straightforward Java Solution with explanation

• The method is quite simple using two points:

``````1, create a boolean[] and initialize the first three(the reason initializing first three is to avoid tail and head overlap)
2, if tail is 2, add two identical item which is different from current head
3, if tail is 1, add 1 different.
4, since it is 1 or 2, just use boolean (1: true, 2: false) to replace int
``````

Here is the code:

``````public class Solution {
public int magicalString(int n) {
// o(n)
if (n == 0) return 0;
if (n < 3) return 1;
int head = 3;
int tail = 2;
boolean[] nums = new boolean[n];
//1:true 2: false
nums[0] = true;
nums[1] = false;
nums[2] = false;
int res = 0;
while (head < n) {
if (!nums[tail]) {
nums[head] = !nums[head-1];
head++;
if (head < n) {
nums[head] = nums[head-1];
head++;
}
} else {
nums[head] = !nums[head-1];
head++;
}
tail++;
}
for(boolean b: nums) {
if (b) res++;
}
return res;
}
}
``````

• Awesome solution! If you use a temp variable and increment it when the value - num[head] is true then the last step to traverse is not required and the algorithm becomes faster.

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