algoadvance

Leetcode 481. Magical String

Problem Statement

A magical string s is a string only consisting of ‘1’ and ‘2’ and obeys the following rules:

  1. The string s is unfolded as follows: s = “1221121221221121122……”
  2. You can see that the first 1 always appears at position 1, and the second 1 always appears at position 5.

Given an integer n, return the number of ‘1’s in the first n number in the magical string.

Example:

Input: n = 6
Output: 3
Explanation: The first 6 elements of magical string s are "122112" and it contains three 1's, so return 3.

Constraints:

Clarifying Questions

  1. Do we need to return the count of ‘1’s within the first n characters if n is greater than the length of the string described in the examples?
    • The length of the string s defined in the unfolded manner continues indefinitely as per the folding rules.
  2. Is the sequence of the string strictly defined by the given example?
    • Yes, we need to follow the rules based on the given structural pattern.

Strategy

  1. Initialize the magical string with its beginning sequence: s = "122".
  2. Use two pointers: one for reading the current value to determine the next segments and one for appending new values to s.
  3. Start processing the string and construct it iteratively until you’ve built up to at least n characters.
  4. Keep count of ‘1’s while building the string.
public class Solution {
    public int magicalString(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1; // Base case, since "122" contains one '1' in the first 3 chars.
        
        StringBuilder s = new StringBuilder("122");
        int count = 1; // Initially, we have one '1'.
        int head = 2, tail = 3; // head for reading, tail for adding new values.
        
        while (s.length() < n) {
            int numToAdd = s.charAt(tail - 1) - '0'; // Determine the number to add based on last character in `s`
            int times = s.charAt(head++) - '0';       // Determine how many times to add it.

            for (int i = 0; i < times; i++) {
                s.append(numToAdd);
                if (numToAdd == 1 && s.length() <= n) {
                    count++;
                }
            }
            tail++;
        }
        
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.magicalString(6)); // Output: 3
    }
}

Time Complexity

Therefore, the overall time complexity for this solution is approximately O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI