Python solution with detailed explanation


  • 0
    G

    Solution

    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
    

Log in to reply
 

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