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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Magical String

Difficulty: Medium

Problem Description

Given an integer n, return the number of '1's in the first n numbers of the magical string s, which consists of only '1's and '2's and follows a specific generation rule based on its prior elements.

Key Insights

  • The magical string starts with "1" and grows based on the count of contiguous '1's and '2's.
  • The characters in the string dictate how many of the next character to append.
  • The first character always starts the sequence, and subsequent characters are determined by the previous counts.
  • Efficiently generating the string up to n while counting '1's can save on space and time.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a dynamic approach to generate the magical string up to the nth character while simultaneously counting the number of '1's. We will maintain a list to build the magical string and use a pointer to track the current position for generating new characters based on the last number in the string.

  1. Start with a list initialized with the first character '1'.
  2. Use a pointer to generate characters based on the value of the last character in the list.
  3. Count the number of '1's as we generate the string.
  4. Stop once we have generated the string up to n characters.

Code Solutions

def magicalString(n: int) -> int:
    if n == 0:
        return 0
    magical = [1]  # Start with the first character '1'
    count_of_ones = 1  # We have one '1' initially
    pointer = 1  # Start generating from the second character

    while len(magical) < n:
        # The current number determines how many of the next character to add
        next_char = 2 if magical[pointer] == 1 else 1
        # Number of times to add the next character
        for _ in range(magical[pointer]):
            if len(magical) < n:
                magical.append(next_char)
                if next_char == 1:
                    count_of_ones += 1
        pointer += 1

    return count_of_ones
← Back to All Questions