In this guide, you will get 481. Magical String LeetCode Solution with the best time and space complexity. The solution to Magical String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
A magical string s consists of only ‘1’ and ‘2’ and obeys the following rules:
The string s is magical because concatenating the number of contiguous occurrences of characters ‘1’ and ‘2’ generates the string s itself.
The first few elements of s is s = “1221121221221121122……”. If we group the consecutive 1’s and 2’s in s, it will be “1 22 11 2 1 22 1 22 11 2 11 22 ……” and the occurrences of 1’s or 2’s in each group are “1 2 2 1 1 2 1 2 2 1 2 2 ……”. You can see that the occurrence sequence is s itself.
Given an integer n, return the number of 1’s in the first n number in the magical string s.
Example 1:
Input: n = 6
Output: 3
Explanation: The first 6 elements of magical string s is “122112” and it contains three 1’s, so return 3.
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 105
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
481. Magical String LeetCode Solution in C++
class Solution {
public:
int magicalString(int n) {
string s = " 122";
for (int i = 3; i <= n; ++i)
if (i % 2 == 1)
s.append(s[i] - '0', '1');
else
s.append(s[i] - '0', '2');
return count(s.begin(), s.begin() + n + 1, '1');
}
}; /* code provided by PROGIEZ */
