We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Magical String

Number: 481

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

A magical string s is a sequence composed of only '1's and '2's. The string is considered magical because if you take the counts of consecutive same characters in s and concatenate them, you get s again. The task is to generate the first n characters of the magical string and count the number of '1's among these n characters.

Key Insights

  • The string is self-generating: the counts of numbers in groups within s reproduce the string.
  • A two-pointer strategy can be used: one pointer (read_ptr) scans the generated part of the string to decide how many times the next digit is appended, and another pointer (the end of the array) reflects the current length.
  • The digit to append alternates between '1' and '2' after each operation.
  • The generation continues until the length of the string reaches n, and during the process, a count of '1's is maintained.

Space and Time Complexity

Time Complexity: O(n) – Each element is generated sequentially until the length n is reached. Space Complexity: O(n) – The generated string is stored up to n characters.

Solution

We use a simulation approach with a two-pointer method. Start with the initial magical string "122". Use a pointer (read_ptr) to get the current count from the string, which tells how many times to append the next character (which alternates between '1' and '2'). Each time characters are appended, check if they are '1' and update the count accordingly. Continue this process until the length of s is at least n. Finally, return the count of '1's in the first n characters.

Code Solutions

# Function to generate the magical string up to n characters and count the number of '1's.
def magicalString(n):
    if n <= 0:
        return 0
    if n <= 3:
        return 1  # For n=1,2,3 the first char is '1' and it's the only '1'
    
    result = ['1', '2', '2']  # initial magical string
    read_ptr = 2             # pointer from which we read the count
    curr_num = '1'           # current number to append (alternates between '1' and '2')
    count_ones = 1           # count of '1's already in result ("1" is present at index 0)
    
    while len(result) < n:
        count = int(result[read_ptr])
        for _ in range(count):
            result.append(curr_num)
            if curr_num == '1' and len(result) <= n:
                count_ones += 1
            if len(result) == n:
                break
        # Alternate the number to be appended for the next group
        curr_num = '2' if curr_num == '1' else '1'
        read_ptr += 1
    
    return count_ones

# Example usage
print(magicalString(6))   # Expected output: 3
← Back to All Questions