public class _38 {
    static class Solution1{
        public String countAndSay(int n) {
            if(n == 1) return "1";
            char pre = '0';
            int count = 0;
            char[] arr = countAndSay(n-1).toCharArray();
            char[] newArr = new char[arr.length*2];
            int idx = 0;
            for(char ch : arr){
                if(pre != '0' && ch != pre){
                    newArr[idx++] =  (char)((int)'0' + (int) count);
                    newArr[idx++] = pre;
                    count = 0;
                }
                count++;
                pre = ch;
            }
            if(count !=0){
                newArr[idx++] =  (char)((int)'0' + (int) count);
                newArr[idx++] = pre;
            }
            return  new String(newArr,0,idx);
        }
    }

    static class Solution2{
        public String countAndSay(int n) {
            if(n == 1) return "1";
            String res = "1";
            for(int i = 2;i <= n;i++){
                char pre = '0';
                int count = 0;
                char[] arr = res.toCharArray();
                char[] newArr = new char[arr.length*2];
                int idx = 0;
                for(char ch : arr){
                    if(pre != '0' && ch != pre){
                        newArr[idx++] =  (char)((int)'0' + (int) count);
                        newArr[idx++] = pre;
                        count = 0;
                    }
                    count++;
                    pre = ch;
                }
                if(count !=0){
                    newArr[idx++] =  (char)((int)'0' + (int) count);
                    newArr[idx++] = pre;
                }
                res = new String(newArr,0,idx);
            }
            return res;
        }
    }
}