[Leetcode] 38. Count and Say

https://leetcode.com/problems/count-and-say/description/?envType=daily-question&envId=2025-04-18

initial

I was so sleepy implementing this but u basically have an input string of "1" and it goes like 1 1s -> 2 1s (val, key).
So i thought of using dictionary and iterating through each character in string. When we are done iterating, we will have some leftover numbers so we need to add.

But my sol is enff cuz i am slicing the lists with prev_idx:cur_idx. I am at top 95% lol but look at my initial attempt first

class Solution:
    def countAndSay(self, n: int) -> str:
        def logic(hola):
            length = len(hola)
            prev=""
            prev_idx,cur_idx=0,0
            ans=""
            while length:
                if prev and hola[cur_idx]!=prev:
                    counter=Counter(hola[prev_idx:cur_idx])
                    for key,val in counter.items():
                        ans+=str(val)
                        ans+=key
                    prev_idx=cur_idx
                prev = hola[cur_idx]
                cur_idx+=1
                length-=1
            counter = Counter(hola[prev_idx:])
            for key, val in counter.items():
                ans += str(val)
                ans += key
            return ans
        tmp = "1"
        if n==1:
            return str(1)
        while n>1:
            tmp = logic(tmp)
            n-=1
        return tmp

sol

A similar approach except here we dont slice the list but we just use a count variable to count how many same numbers we have seen so far. If the current number is different, then we append count and the previous number

Also we iter up to n-1 cuz if n=1 edge case, the for loop doesnt run and we return '1' straightway very clever

we initialise tmp list to store both counts and the numbers and we ''.join them up at the end.

class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        s = '1'
        for i in range(n-1):
            count = 1
            temp = []
            for index in range(1, len(s)):
                if s[index] == s[index-1]:
                    count += 1
                else:
                    temp.append(str(count))
                    temp.append(s[index-1])
                    count = 1
            temp.append(str(count))
            temp.append(s[-1])
            s = ''.join(temp)
        return s

complexity

In general, to calculate the n-th term, we iterate n-1 times. In the i-th iteration (where i goes from 1 to n−1), we process the (i)-th term to generate the (i+1)-th term. The time taken in each iteration is directly proportional to the length of the string we are processing in that iteration.

Let L(n) denote the length of the n-th count-and-say string. The total time taken to generate the n-th string is roughly the sum of the lengths of all the preceding strings:

Time ≈L(1)+L(2)+L(3)+...+L(n−1)

Now, let's consider how the length of the string grows. While it's not a strict doubling, it tends to increase significantly. The growth factor is related to the maximum number of consecutive identical digits. It's known that the length of the n-th string L(n) grows roughly as O(c
n
) where c≈1.303577 (related to the plastic constant).

However, if we consider the time complexity in terms of the length of the final n-th string, the dominant operation in the last iteration (to produce the n-th string) takes O(L(n−1)) time, which is of the same order as O(L(n)).

for space it is
length of the final string