Count and Say | LeetCode | InterviewBit | Solution Explained

Count and Say is an interesting problem. It only requires the knowledge of basics of strings and nothing else. I explain the solution simply with code. Problem Links: LeetCode Count and Say InterviewBit Count and Say.

0. Count and Say: Problem Discussion

0.0. IO Format

• Given: integer n, 1 <= n <= 30
• Goal: return a string which is: count the number of consecutive characters & say them

0.1. Examples

To understand the problem, here are some examples:

1. Count and Say: Observations & Logic

1.0. Intuitions

All right. What do we observe?

• for getting the answer of n, we need the answer for n-1
• we take the answer of n-1 and create a frequency table for consecutive numbers: for example, if we have 111, we write it as (f, x) --> (3, "1") --> "31" where f is the frequency of the consecutive x numbers.

And that’s all we have to implement!

2. Count and Say: Implementation

2.0. Code

class Solution:
    def countAndSay(self, n: int) -> str:
        prev = "1"
        
        while (n := n-1):
            # PART1: FREQUENCY TABLE INTERMEDIATE
            table = []
            i = 0
            while i < len(prev):
                table.append([1, prev[i]])
                while i+1 < len(prev) and prev[i+1] == prev[i]:
                    table[-1][0] += 1
                    i += 1
                i += 1
            
            # PART2: CONVERT BACK TO STRING
            prev = "".join(str(f)+x for f, x in table)

        return prev

2.1. Complexity Analysis

• Time: O(NL), N the input given and L the max length of the “prev” string
• Space: O(L), worst case, we have to store a long frequency table of 1 amounts of non-consecutive characters.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.