481. Magical String

MediumTwo PointersString
Leetcode Link

Problem Description

The problem presents a unique sequence called a "magical string" that is built based on its own sequence of numbers. We start with a string s that only contains the characters '1' and '2'. The magic is that when we group the characters in s by the count of consecutive '1's and '2's, these grouped counts form the same string s.

As an example, we start with the known sequence: "1221121221221121122...". Grouping the consecutive characters yields "1 22 11 2 1 22 1 22 11 2 11 22 ...", and then the counts of '1's and '2's in these groups are "1 2 2 1 1 2 1 2 2 1 2 2 ...", which is the same as the original sequence s.

The task is to determine the count of '1's in the first n characters of the magical string s. Specifically, given an integer n, return how many '1's appear in the initial segment of length n in the string s.

Intuition

To solve this problem, we don't need to generate the entire string, which could be very long. Instead, we can build the string s only as far as necessary to count the number of '1's within the first n characters.

The solution uses a list s to simulate the magical string and a pointer i to keep track of where in s we are currently looking to determine how many times to repeat the next character. We begin with the known start of the magical string as [1, 2, 2].

The core idea is to iteratively extend the magical string based on its definition. For each step, we look at the value of s[i], which tells us how many times to repeat the next character. We alternate the characters to add based on the last character in the string: if it's a '1', we add '2's; if it's a '2', we add '1's. The number of characters to add is equal to the current value of s[i].

The use of pre helps us know what the last character was (either '1' or '2'), and cur is used to determine what the next character should be, by switching between '1' and '2'.

We continue extending the string until its length is at least n. Once the length of s reaches n, we simply take the first n elements of s and count the number of '1's to get our answer.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used in a depth first search?

Solution Approach

The implementation relies on a simple Python list s to simulate the construction of the magical string. An integer i serves as a pointer that moves through the list, indicating how many times the next character should be repeated. Here's how the implementation unfolds:

  1. We initialize the representation of the magical string as s = [1, 2, 2]. This is because the sequence always starts with "122".

  2. We set the pointer i = 2. This is because s[2] points to the second '2' in the initial list, which indicates that the next sequence to be added should consist of two numbers. The pointer i will indicate which number in s we should look at to determine the next sequence to append to s.

  3. We then enter a while loop which will run as long as the length of s is smaller than n, ensuring that we build enough of the magical string to count the number of '1's in the first n characters.

  4. Inside the loop, we first store the last element of the current string in the variable pre. This is either a 1 or a 2, and it represents the last character in the string.

  5. Next, we calculate cur as 3 - pre. Since we only have '1' and '2' in our sequence, if the last character (pre) is '1', cur will be '2' (since 3 - 1 = 2), and if it's '2', cur will be '1'.

  6. The next step is to extend the list s by adding cur repeated s[i] times. This is akin to saying "if we have a '2' in s[i], and cur is '1', then append '1' to s two times." We append [cur] * s[i] to s.

  7. We then increment i by 1 to move the pointer to the next character in s.

  8. Once we exit the while loop, it means we've built a section of the magical string that is at least as long as n. The last step is to return the count of '1's in the first n characters of s by using s[:n].count(1).

This approach is efficient because it constructs only as much of the magical string as is necessary to determine the number of '1's within the first n elements. It uses simple list operations and arithmetic to achieve this task.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we are asked to find the number of '1's in the first 10 characters of the magical string s.

  1. We start off by initializing our list s with the known beginning of the magical string: [1, 2, 2].

  2. The pointer i is initially set to 2, since s[2] points to '2', which will determine what we append next to s.

  3. Our while loop continues as long as the length of s is less than 10 (the n value in our example). At the start, the length of s is 3, so we enter the loop.

  4. The last element, pre, of the current string s is 2.

  5. We calculate cur as 3 - pre. Since pre is 2, cur becomes 1.

  6. We extend s by adding cur repeated s[i] times. In this case, since s[i] is 2 and cur is 1, we append two '1's to s, resulting in s becoming [1, 2, 2, 1, 1].

  7. We then increment i by 1, moving the pointer to the next character in s, so i is now 3.

  8. Now, pre is 1 (the last element in s), so now cur will be 3 - pre, which is 2. s[i] is 1, so we append one '2' to s, changing s to [1, 2, 2, 1, 1, 2].

  9. We repeat steps 4 through 7, with i now at 4. s[i] is 1, the current pre is 2, so cur is 1. We add one '1' to s to get [1, 2, 2, 1, 1, 2, 1].

  10. Continuing this process, we increment i, calculate cur, and extend s until s is at least 10 characters long. After a few iterations, s is [1, 2, 2, 1, 1, 2, 1, 2, 2, 1], and the length of s is 10.

  11. The loop stops since s now has a length of 10. We count the number of '1's in s[:10], which is 5.

Thus, for n = 10, our function would return 5, as there are five '1's in the first 10 characters of the magical string s.

Solution Implementation

1class Solution:
2    def magicalString(self, n: int) -> int:
3        # Initialize the magical string with the known starting sequence
4        magical_str = [1, 2, 2]
5      
6        # Use index to track the position in the string for generating the next elements
7        index = 2  
8      
9        # Generate the magical string until its length is at least 'n'
10        while len(magical_str) < n:
11            # Get the last value in the magical string
12            last_value = magical_str[-1]
13          
14            # The current value to be appended is the "opposite" of the last value (1 switches to 2, and 2 switches to 1)
15            current_value = 3 - last_value
16          
17            # Append 'current_value' to the list as many times as the value at the current 'index'
18            magical_str.extend([current_value] * magical_str[index])
19          
20            # Move to the next index
21            index += 1
22      
23        # Slice the magical string until 'n' and count the occurrences of `1`
24        return magical_str[:n].count(1)
25
1class Solution {
2    public int magicalString(int n) {
3        // Initialize the magical string as a list with the first three numbers
4        List<Integer> magicalStr = new ArrayList<>(Arrays.asList(1, 2, 2));
5
6        // Use a pointer to iterate through the magical string to generate the next numbers
7        int i = 2; // Starting from index 2 because the first three numbers are already in the list
8        while (magicalStr.size() < n) {
9            int lastNum = magicalStr.get(magicalStr.size() - 1); // Get the last number in the current magical string
10            int nextNum = 3 - lastNum; // Calculate the next number (if lastNum is 1, then nextNum is 2; if lastNum is 2, then nextNum is 1)
11
12            // Add 'nextNum' to the magical string 's.get(i)' times as per the current number's frequency
13            for (int j = 0; j < magicalStr.get(i); ++j) {
14                magicalStr.add(nextNum);
15            }
16
17            i++; // Move to the next number
18        }
19
20        // Count the number of occurrences of 1 in the first 'n' elements of the magical string
21        int countOnes = 0;
22        for (int idx = 0; idx < n; ++idx) {
23            if (magicalStr.get(idx) == 1) {
24                countOnes++;
25            }
26        }
27      
28        // Return the count of 1's in the first 'n' elements of the magical string
29        return countOnes;
30    }
31}
32
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int magicalString(int n) {
7        std::vector<int> magical_seq = {1, 2, 2}; // Initialize the magical sequence with its first three elements
8
9        // Use 'index' to iterate through the magical sequence
10        // The loop continues until the size of magical_seq is at least n
11        for (int index = 2; magical_seq.size() < n; ++index) {
12            int last_number = magical_seq.back(); // Get the last number in the current sequence
13            int next_number = 3 - last_number; // Determine the next number to add, which will be 1 if the last is 2, and 2 if the last is 1
14
15            // Append the next_number to the sequence s[i] times where s[i] is the current element at position i
16            // This loop controls the count of the next number to be appended
17            for (int count = 0; count < magical_seq[index]; ++count) {
18                magical_seq.emplace_back(next_number); // Append the number to the end of the sequence
19            }
20        }
21
22        // Count the number of 1's up to the nth element and return that count
23        return std::count(magical_seq.begin(), magical_seq.begin() + n, 1);
24    }
25};
26
1function magicalString(n: number): number {
2    // Initialize the magical string with the known beginning sequence
3    let magicalStr = [...'1221121'];
4    // Initialize the index for counting group occurrences
5    let readIndex = 5;
6
7    // Generate the magical string up to the required length 'n'
8    while (magicalStr.length < n) {
9        // Get the last character of the current magical string
10        const lastChar = magicalStr[magicalStr.length - 1];
11        // Append the opposite character to the string ('1' becomes '2', and '2' becomes '1')
12        magicalStr.push(lastChar === '1' ? '2' : '1');
13        // If the current read index character is '2', repeat the action once more
14        if (magicalStr[readIndex] !== '1') {
15            magicalStr.push(lastChar === '1' ? '2' : '1');
16        }
17        // Move to the next index
18        readIndex++;
19    }
20  
21    // Calculate the number of '1's in the first 'n' characters of the magical string
22    return magicalStr.slice(0, n).reduce((count, char) => count + (char === '1' ? 1 : 0), 0);
23}
24
Not Sure What to Study? Take the 2-min Quiz：

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Time and Space Complexity

Time Complexity

The time complexity of the function primarily comes from the while loop that generates the magical string until its length is at least n. In each iteration, the loop appends up to s[i] elements to the list s where s[i] could be either 1 or 2. This results in a maximum of 2 additions per iteration. However, since each iteration of the loop adds at least one element, and we iterate until we have n elements, the overall time complexity can be approximated as O(n).

Space Complexity

The space complexity of this function is also defined by the size of the list s, which grows to match the input n in the worst-case scenario. Since we need to store each element of the magical string up to the nth position, the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫