grid47 Exploring patterns and algorithms
Sep 19, 2024
4 min read
Solution to LeetCode 481: Magical String Problem
A magical string consists of only ‘1’ and ‘2’ and follows a special rule: the number of consecutive occurrences of characters ‘1’ and ‘2’ generates the string itself. Given an integer n, return the number of ‘1’s in the first n characters of the magical string.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer `n`, the length of the desired substring of the magical string.
Example: n = 7
Constraints:
• 1 <= n <= 10^5
Output: Return the number of '1's in the first `n` characters of the magical string.
Example: Output: 4
Constraints:
• The result will be a non-negative integer.
Goal: Generate the magical string up to `n` characters and count the number of '1's.
Steps:
• 1. Start with the base string '122'.
• 2. Generate the magical string by adding segments based on the number of previous occurrences.
• 3. For each segment, append the opposite digit (either '1' or '2') based on the previous occurrence.
• 4. Once the string is generated up to `n` characters, count the number of '1's in the substring.
Goal: The constraints on the input are as follows.
Steps:
• 1 <= n <= 10^5
Assumptions:
• The value of `n` will always be within the given range.
• Input: n = 7
• Explanation: The first 7 characters of the magical string are '1221121'. This string has four '1's, so the output is 4.
• Input: n = 3
• Explanation: The first 3 characters of the magical string are '122'. This string has two '1's, so the output is 2.
Approach: The approach involves constructing the magical string by iterating through the number of occurrences of '1' and '2' and generating the corresponding sequence.
Observations:
• We can generate the magical string by appending based on the previous occurrences of '1' and '2'.
• The string grows gradually, so we can stop once we have the first `n` elements.
• We need to efficiently construct the magical string and keep track of the occurrences of '1's.
Steps:
• 1. Start with the base string '122'.
• 2. Use a loop to expand the string by adding segments of '1' and '2' based on the number of occurrences in the previous elements.
• 3. After generating the first `n` elements, count the occurrences of '1'.
Empty Inputs:
• The input will always have at least 1 element (n >= 1).
Large Inputs:
• For large values of `n`, the algorithm should handle constructing the string efficiently up to 10^5 characters.
Special Values:
• When `n = 1`, the string is just '1', so the output will be 1.
Constraints:
• The solution should be able to handle up to 10^5 elements in the magical string.
intmagicalString(int n) {
string s ="122";
int i =2;
while(s.size() < n)
s += string(s[i++] -'0', s.back() ^3);
return count(s.begin(), s.begin() + n, '1');
}
1 : Function Definition
intmagicalString(int n) {
Defines the `magicalString` function, which generates a magical string up to the `n`th character and counts the number of '1's.
2 : String Initialization
string s ="122";
Initializes the string `s` with the value "122". This is the base case for the magical string.
3 : Variable Initialization
int i =2;
Initializes the variable `i` to 2. This will be used to track the current index in the string while constructing new elements.
4 : Loop
while(s.size() < n)
Starts a `while` loop that continues to run until the size of the string `s` reaches or exceeds the given number `n`.
5 : String Manipulation
s += string(s[i++] -'0', s.back() ^3);
Appends new characters to the string `s`. The number of new characters is determined by the value of the current character at index `i`. The new characters are the inverse of the last character in the string.
6 : Return Statement
returncount(s.begin(), s.begin() + n, '1');
Returns the count of '1's in the string `s` from the beginning up to the `n`th position.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we generate the magical string up to `n` characters and count the number of '1's in the first `n` elements.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we store the magical string up to `n` characters.
