Last updated on February 2nd, 2025 at 04:54 am
Here, we see a Magical String LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
String
Companies
Level of Question
Medium
Magical String LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in this code is “String Construction with Simulation”. This pattern involves simulating the construction of a sequence or string based on specific rules and conditions.
3. Code Implementation in Different Languages
3.1 Magical String C++
class Solution {
public:
int magicalString(int n) {
if( n <= 3) return 1;
string s = "122";
int i = 2;
while(s.size() < n)
{
if(s[i]=='1')
{
if(s[s.size()-1] == '2') s.push_back('1');
else s.push_back('2');
}
else
{
if(s[s.size()-1] == '2') s += "11";
else s += "22";
}
i++;
}
int cnt = count(s.begin(),s.begin() + n,'1');
return cnt;
}
};
3.2 Magical String Java
class Solution {
public int magicalString(int n) {
StringBuilder st=new StringBuilder("122");
int p1=2,p2=st.length(),count=0;
while(st.length()<n){
if(st.charAt(p1)=='1'){
if(st.charAt(p2-1)=='1')
st.append(2);
else
st.append(1);
p2++;
}
else{
if(st.charAt(p2-1)=='1')
st.append(22);
else
st.append(11);
p2+=2;
}
p1++;
}
for(int i=0;i<n;i++){
if(st.charAt(i)=='1')
count++;
}
return count;
}
}
3.3 Magical String JavaScript
var magicalString = function(n) {
const arr = ['1', '2', '2'];
let i = 0;
let res = 1;
while (arr.length < n) {
let val = i % 2 === 0 ? '1' : '2';
let isOne = val === '1';
if (arr[i + 2] === '1') {
arr.push(val);
if (isOne) res++;
} else {
arr.push(val);
if (isOne) res++;
if (arr.length >= n) break;
arr.push(val);
if (isOne) res++;
}
i++;
}
return res;
};
3.4 Magical String Python
class Solution(object):
def magicalString(self, n):
if n == 0:
return 0
s = [1, 2, 2]
i = 2
while len(s) < n:
s += [3 - s[-1]] * s[i]
i += 1
return s[:n].count(1)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |
- The code uses a String Construction with Simulation pattern to solve the problem.
- It dynamically constructs the magical string based on the rules and counts the number of
1s in the firstncharacters. - The time complexity is O(n), and the space complexity is O(n) due to the storage of the string.