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:

Count and Say: When n = 1, ans = "1"
Count and Say: When n = 1, ans = “1”
 Count and Say: When n = 2, we say that for n = 1, the answer contained 1 (amounts of) 1.
Count and Say: When n = 2, we say that for n = 1, the answer contained 1 (amounts of) 1.
 Count and Say: When n = 2, we say that for n = 2, the answer contained 2 (amounts of) 1.
Count and Say: When n = 3, we say that for n = 2, the answer contained 2 (amounts of) 1.
 Count and Say: When n = 4, we say that for n = 3, the answer contained 1 (amounts of) 2 and 1 (amounts of) 1.
Count and Say: When n = 4, we say that for n = 3, the answer contained 1 (amounts of) 2 and 1 (amounts of) 1.
Count and Say: When n = 5 and 6, we do the same.
Count and Say: When n = 5 and 6, we do the same.

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.

Avatar for Tanishq Chaudhary

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

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.