38. Count and Say

time: O(n*n/2) maybe?

space: O(n)

class Solution {
    public String countAndSay(int n) {
        String res = "1";
        for (int i = 1 ; i < n; i++) {
            res = cal(res);
        }
        return res;
    }

    /*
 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
 10.   13211311123113112211

    */
    private String cal(String s) {
        int i = 0;
        StringBuilder sb = new StringBuilder();

        while (i < s.length()) {
            char temp = s.charAt(i);
            int count = 0;
            
            while (i < s.length() && s.charAt(i) == temp) {
                i++;
                count++;
            }
            sb.append(count);
            sb.append(temp);
        }
        return sb.toString();
    }
}