java straightforward, o(n) time & space


  • 0
    W
    public class Solution {
        public int magicalString(int n) {
            if (n <= 0) return 0; 
            int[] dp = new int[n]; // dp is the magical string
            dp[0] = 1; 
            int j = 0; 
            int i = 1;
            while (i < n) {
                if (dp[i-1] == 1) dp[i] = 2; 
                else dp[i] = 1; 
                j++; 
                int count = dp[j]; 
                int digit = dp[i];
                for (int k = 0; k < count && i < n; k++, i++) {
                    dp[i] = digit;
                }
                
            }
            int count1 = 0; 
            for (int k = 0; k < n; k++) {
                if (dp[k] == 1) count1++; 
            }
          //  System.out.println(Arrays.toString(dp)); 
            return count1; 
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.