Magical String https://leetcode.com/problems/magical-string/
Incrementally build sequence using next group id: O(N)
- Initialze sequence as 1,2,2. This represents the group 0 and group 1. The next group (id = 2) will comprise of 1's and the number of 1s (freq) should be so_far[grp_id] which is 2. So we add 1,1 to so_far and it is now: 1,2,2,1,1
- In this manner, we can keep building the string and test for length after addition of every group. Note the maximum frequency can be only 2. Be careful to adjust for an extra one as shown below in the code.
class Solution(object): def magicalString(self, n): """ :type n: int :rtype: int """ if n == 0: return 0 elif n <= 3: return 1 else: so_far, grp, ones =[1,2,2], 2, 1 while len(so_far) < n: freq, item = so_far[grp], 1 if grp % 2 == 0 else 2 for _ in range(freq): so_far.append(item) ones, grp = ones + freq if item == 1 else ones, grp + 1 if len(so_far) == n: return ones else: return ones-1 if so_far[-1] == 1 else ones