Programming Challenge 15: Count-and-Say Sequence in Python

Today, we are back with another Python programming challenge. This time, we’ll work on the Count-and-Say problem from Leetcode. This challenge requires us to write a function that gives the n^th term of the count-and-say sequence in Python.

What is the Count-and-Say Sequence

The count-and-say sequence, also known as the look-and-say sequence, is a sequence of integers that starts with 1.

Each subsequent integer in the sequence is generated by counting and reading off the digits in the previous integer, counting the number of digits in groups of the same digit.

Confused? The easiest way to understand count-and-say is to illustrate the steps using a string of letters.

Suppose I have the string

'aaabbaccd'

If I count-and-say the letters in the string, I’ll read the string as

Three 'a's, two 'b's, one 'a', two 'c's, one 'd'

since there are three ‘a’s in the string, followed by two ‘b’s, one ‘a’ and so on.

Now, if instead of a string of letters, suppose I have a string of digits, such as the string

'1125558'

I’ll read the string as

Two '1's, one '2', three '5's, one '8'

since there are two ‘1’s, one ‘2’, three ‘5’s and one ‘8’ in the string.

This is the main idea behind the count-and-say sequence.

One difference between the count-and-say sequence and what we did above is the count-and-say sequence expresses the frequency of each digit using numbers (instead of text such as ‘one’, ‘two’ and ‘three’).

Hence, the string above will be expressed as

21123518

Based on the concept covered above, we can generate the count-and-say sequence.

As mentioned previously, this sequence starts with the integer 1. To generate the other numbers in the sequence, we count-and-say the digits in the previous integer.

The first six terms of the sequence are given below:

1
11 (because the previous integer has one 1)
21 (because the previous integer has two 1s)
1211 (because the previous integer has one 2, followed by one 1)
111221 (because the previous integer has one 1, one 2 and two 1s)
312211 (because the previous integer has three 1s, two 2s and one 1)

Our job today is to write a function called countAndSay() that accepts one argument – n.

The function returns the n^th term of the count-and-say sequence as a string. For instance, if n equals 5, the function gives the 5^th term in the sequence, which equals '111221'.

Suggested Approach

To solve this problem, let’s consider the case where n equals 5.

To get the 5^th term for the count-and-say sequence, we need the 4^th term, which equals '1211'.

Let’s store this string in a variable called prevString.

We’ll iterate through prevString one character at a time to do the counting.

Say we store the result of the counting-and-saying in a variable called res and use a variable called count to keep track of the number of times a digit appears. At the beginning, res = '' and count = 1.

There are two cases where we need to update res:

Case 1 – When we find a new digit in prevString
Case 2 – After we finish iterating through the entire string.

Here’s how it works.

We’ll start with the second digit in prevString ('1211') and check if this digit is the same as the previous digit.

In this case, '2' is not the same as '1'. Hence, we need to update res (Case 1). Specifically, we need to update res to '11', since there is one ‘1’ previously.

Next, we move on to the third digit. This digit ('1') is again not the same as the previous digit ('2'). Hence, we need to update res (Case 1) again.

This time, we append the string '12' (since there is one ‘2’ previously) to res.

res becomes '1112'.

Next, we move on to the fourth digit. This digit ('1') is the same as the previous digit ('1'). Hence, we do not need to update res. However, we need to update count to 2.

Finally, after iterating through all the digits in prevString, we need update res one last time (Case 2) by appending '21' to res.

res becomes '111221', which is the required answer.

Based on the approach described above, try solving today’s challenge yourself.

Note that the approach described above starts with the 4^th term ('1211') in the count-and-say sequence. In your solution, you need to figure out how to start with the 1^st term ('1') in the sequence and use that to generate subsequent terms until you get the n^th term.

Suggested Solution

Here’s the suggested solution for the count-and-say sequence problem in Python:

def countAndSay(n):

    if n == 1:
        return '1'

    prevString = '1'
    
    for i in range(1, n):
        res = ''
        count = 1

        for j in range(1, len(prevString)):
            if prevString[j] == prevString[j-1]:
                count += 1
            else:
                res = res + str(count) + str(prevString[j-1])
                count = 1

        res = res + str(count) + str(prevString[-1])
        prevString = res

    return prevString

111221