Generate the nth term of the count-and-say sequence.
Input: n=1 → Output: "1"
Input: n=4 → Output: "1211". 1 → 11 → 21 → 1211
Build each term by reading off consecutive groups of same digits from previous term.
- Start with "1"
- For each step 1..n-1: scan current string for runs of same digit
- Append count then digit to next string
- Repeat n-1 times
public String countAndSay(int n) {
String s = "1";
for (int i = 1; i < n; i++) {
StringBuilder sb = new StringBuilder();
int j = 0;
while (j < s.length()) {
char c = s.charAt(j);
int count = 0;
while (j < s.length() && s.charAt(j) == c) { j++; count++; }
sb.append(count).append(c);
}
s = sb.toString();
}
return s;
}
- Time Complexity: O(n * 2^n)
- Space Complexity: O(2^n)