lc-38

//The count-and-say sequence is a sequence of digit strings defined by the recur
//sive formula: 
//
// 
// countAndSay(1) = "1" 
// countAndSay(n) is the way you would "say" the digit string from countAndSay(n
//-1), which is then converted into a different digit string. 
// 
//
// To determine how you "say" a digit string, split it into the minimal number o
//f substrings such that each substring contains exactly one unique digit. Then fo
//r each substring, say the number of digits, then say the digit. Finally, concate
//nate every said digit. 
//
// For example, the saying and conversion for digit string "3322251": 
//
// Given a positive integer n, return the nth term of the count-and-say sequence
//. 
//
// 
// Example 1: 
//
// 
//Input: n = 1
//Output: "1"
//Explanation: This is the base case.
// 
//
// Example 2: 
//
// 
//Input: n = 4
//Output: "1211"
//Explanation:
//countAndSay(1) = "1"
//countAndSay(2) = say "1" = one 1 = "11"
//countAndSay(3) = say "11" = two 1's = "21"
//countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
// 
//
// 
// Constraints: 
//
// 
// 1 <= n <= 30 
// 
// Related Topics String 
// 👍 1661 👎 3967


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String countAndSay(int n) {
        String cur = "1";

        for (int i = 1; i < n; i++) {
            cur = getNext(cur);
        }

        return cur;
    }

    String getNext(String last) {
        char lastCh = 0;
        StringBuilder sb = new StringBuilder();
        int curNumber = 0;

        for (char ch : last.toCharArray()) {
            if (lastCh != 0 && ch != lastCh) {
                sb.append(curNumber);
                sb.append(lastCh);
                curNumber = 0;
            }
            lastCh = ch;
            curNumber++;
        }

        sb.append(curNumber);
        sb.append(lastCh);

        return sb.toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)