Skip to content

481. Magical String 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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');
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int magicalString(int n) {
    StringBuilder sb = new StringBuilder(" 122");
    int ans = 0;

    for (int i = 3; i <= n; ++i)
      if (i % 2 == 1)
        sb.append(String.valueOf('1').repeat(sb.charAt(i) - '0'));
      else
        sb.append(String.valueOf('2').repeat(sb.charAt(i) - '0'));

    for (int i = 0; i <= n; ++i)
      if (sb.charAt(i) == '1')
        ++ans;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def magicalString(self, n: int) -> int:
    s = [' ', '1', '2', '2']

    for i in range(3, n + 1):
      if i % 2 == 1:
        s.extend(['1'] * (int(s[i])))
      else:
        s.extend(['2'] * (int(s[i])))

    return sum(1 for c in s[:n + 1] if c == '1')