Very Straightforward and simple Java solution O(n)


  • 6
    C
    public int magicalString(int n) {
            StringBuilder magic = new StringBuilder("1221121221221121122");
            int pt1 = 12, pt2 = magic.length(), count = 0; //initiate pointers
            //generate sequence directly
            while(magic.length() < n){
                if(magic.charAt(pt1) == '1'){
                    if(magic.charAt(pt2-1) == '1') magic.append(2);
                    else magic.append(1);
                    pt2++;
                }else{ //==2
                    if(magic.charAt(pt2-1) == '1') magic.append(22);
                    else magic.append(11);
                    pt2+=2;
                }
                pt1++;
            }
            for(int i=0;i<n;i++)
                if(magic.charAt(i)=='1') count++;
            return count;
        }
    

  • 0

    Thank you for the solution!One thing I notice that you initialize the StringBuilder as a String with length 12,instead of "1",why?


  • 0
    C

    @bxiao0801 note that in the problem descripition, there are "2 strings". One is the magic string itself(longer), one is the "occurrence string(shorter)"
    so look:

    index        0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18 
    magic string 1  2  2  1  1  2  1  2  2  1   2   2   1   1   2   1   1   2   2
    occur string 1    2    2    1  1    2   1     2       2     1      2      2         //length 12
    

    notice how the numbers match. The length of the occurrence string is 12, so if you want to keep generating the magic string, the pointer should point to its index 12 element


  • 0
    R

    Actually, you can build the string with just "122". See in this example: https://discuss.leetcode.com/topic/74640/short-python-using-queue


  • 1
    C

    @randall.tom1868 Yes i saw that. I just did it in a more intuitive way.


  • 0
    X

    Here is a shorter version:

    public int magicalString(int n) {
        StringBuilder magic = new StringBuilder("122");
        int idx = 2;
    
        while (magic.length() < n) {
            final char ch = magic.charAt(magic.length() - 1) == '1' ? '2' : '1';
    
            for (int i = 0, m = Math.min(magic.charAt(idx++) - '0', n - magic.length()); i < m; i++) {
                magic.append(ch);
            }
        }
    
        return (int) magic.chars().limit(n).filter(i -> i == '1').count();
    }
    

Log in to reply
 

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