38. Count and Say

sliding window

class Solution:
    def countAndSay(self, n: int) -> str:
        res = '1'
        for x in range(1, n):
            s, i, j, n = '', 0, 1, len(res)
            while i < n:
                while j < n and res[j] == res[i]:
                    j += 1
                s += str(j - i) + res[i]
                i = j
            res = s
        return res

class Solution:
    def countAndSay(self, n: int) -> str:
        def cas(s):
            res = ''
            i, j, n = 0, 1, len(s)
            while i < n:
                while j < n and s[j] == s[i]:
                    j += 1
                res += str(j - i) + s[i]
                i = j
            return res
        res = '1'
        for x in range(1, n):
            res = cas(res)
        return res

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

    string helper(const string &s) {
        int n = s.length(), cnt = 0;
        string res;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            int cnt = 0, j = i;
            for (; j < n && s[j] == c; ++j) {
                ++cnt;
            }
            res += to_string(cnt);
            res += c;
            i = j - 1;
        }
        return res;
    }
};

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

    string helper(string &s) {
        s += "#";
        char prev = '#';
        int b = 0;
        int n = s.length();
        string res;
        for (int i = 0; i < n; ++i) {
            if (s[i] != prev) {
                if (i - b > 0) {
                    res += to_string(i - b);
                    res += prev;
                }
                prev = s[i];
                b = i;
            }
        }
        return res;
    }
};

iterative

class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        while (n-- > 1) {
            string s;
            int l = 0, r = 1, len = size(res);
            while (l < len) {
                while (r < len && res[r] == res[l]) ++r;
                s += to_string(r - l) + res[l];
                l = r;
            }
            swap(res, s);
        }
        return res;
    }
};

class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        while (n-- > 1) { // 要从1开始，因为0已经数过了
            int len = size(res);
            res += "#"; // padding以防最后越界
            string s;
            int cnt = 1; // cnt要从1开始，因为每次res[i] != res[i + 1]的时候会少做一次cnt++
            for (int i = 0; i < len; ++i) {
                if (res[i] == res[i + 1]) {
                    ++cnt;
                } else {
                    s += to_string(cnt) + res[i];
                    cnt = 1;
                }
            }
            swap(res, s);
        }
        return res;
    }
};

class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        for (int i = 1; i < n; ++i) {
            res += "#";
            char prev = '#';
            int b = 0;
            int len = res.length();
            string s;
            for (int i = 0; i < len; ++i) {
                if (res[i] != prev) {
                    if (i - b > 0) {
                        s += to_string(i - b);
                        s += prev;
                    }
                    prev = res[i];
                    b = i;
                }
            }
            swap(res, s);
        }
        return res;
    }
};