LeetCode. 38. Count and Say

[Link] https://leetcode.com/problems/count-and-say/

Approach

Start with the first term, "1". To produce each next term, scan the current term from left to right, identify each maximal run of equal digits, and append the run’s length followed by its digit. The scan advances past the entire run, so every digit is encoded exactly once. Repeating this transformation n - 1 times produces the requested term.

Let L_k be the length of the term after round k. Processing a term takes time proportional to its length, and appending creates the next term, so total time is O(sum of generated term lengths). The current and next terms are the only strings retained during a round; working space is O(current term length) (the next term is bounded by a constant factor of the current term length).

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public String countAndSay(int n) {
        String term = "1";

        for (int round = 1; round < n; round++) {
            StringBuilder next = new StringBuilder();
            int i = 0;

            while (i < term.length()) {
                char digit = term.charAt(i);
                int end = i + 1;
                while (end < term.length() && term.charAt(end) == digit) {
                    end++;
                }

                next.append(end - i).append(digit);
                i = end;
            }

            term = next.toString();
        }

        return term;
    }
}