Look And Say Sequence In C++

In this guide, we will explore the Look-and-Say Sequence along with its various approaches, illustrations, time complexity analysis, and space complexity evaluation.

What is the Look-and-Say Sequence?

The Look-and-say Sequence, also known as the "Count-and-say Sequence," is a series of numbers where each term after the first one is generated by describing the previous term using a sequence of consecutive digits. The sequence follows a pattern of analyzing the digits in the current term, tallying the consecutive occurrences of each digit, and then verbalizing the count followed by the digit. This method is iterated to produce every consecutive term in the sequence.

Examples of the look-and-say sequence include: 1, 11, 21, 1211, 111221, 312211, 13112221, and so forth.

The Look-and-Say Sequence's Structure:

• ✅ In the Look-and-Say sequence, "1" is the first term.
• ✅ Since there is only one "1" in the first word, the second term, "11", is produced by interpreting the first term as "One 1."
• ✅ Reading the second term as "Two 1s", the third term, "21", is produced.
• ✅ The "1211" is the fourth term that results from interpreting the third term as "One 2, One 1".
• ✅ The following term is created by reading the counts and digits of the previous term, continuing this pattern.

Method 1: Simple method

Example:

Let's consider an example to demonstrate the Look-and-Say Sequence in C++.

#include <iostream>
#include <string>
using namespace std;
string generateLookAndSay(int n)
{
    if (n == 1) return "1";
    if (n == 2) return "11";
    string currentTerm = "11";
    for (int q = 3; q <= n; q++)
    {
        currentTerm += '$';
        int length = currentTerm.length();
        int count = 1;
        string nextTerm = "";
        for (int k = 1; k < length; k++)
        {
            if (currentTerm[k] != currentTerm[k - 1])
            {
                nextTerm += to_string(count);
                nextTerm += currentTerm[k - 1];
                count = 1;
            }
            else
            {
                count++;
            }
        }
        currentTerm = nextTerm;
    }
    return currentTerm;
}
int main()
{
    int n;
    cout << "Enter the term number for the Look-and-Say sequence: ";
    cin >> n;
    cout << "The " << n << "th term in the Look-and-Say sequence is: " << generateLookAndSay(n) << endl;
    return 0;
}

Output:

Enter the term number for the Look-and-Say sequence: 5
The 5th term in the Look-and-Say sequence is: 111221

Complexity Analysis:

• ✅ Time Complexity: O(n^2)
• ✅ Auxiliary Space: O(1)

Explanation:

This C++ code utilizes input from the user to create the Nth phrase of the Look-and-Say sequence. By progressing from the third item to the Nth item, the generateLookAndSay(int n) function constructs each item by analyzing and tallying the digits that precede it. To form the subsequent item, the internal loop calculates the frequency of each digit, while the outer loop moves through each item. After generating the specified item, the program displays it.

Method 2: Using STL

In the "Look-and-Say" sequence, the objective is to efficiently monitor the consecutive digits' quantity when generating the next sequence. This approach involves utilizing an unordered_map to iterate over the existing series, tallying the occurrences of each digit, and subsequently constructing the next sequence based on these tallies.

Example:

Let's explore another instance to demonstrate the Look-and-Say Sequence in C++ leveraging the STL library.

#include <bits/stdc++.h>
using namespace std;
string generator(string str)
{
    string ans = "";
    unordered_map<char, int> tempCount;
    for (int q = 0; q < str.length() + 1; q++)
    {
        if (tempCount.find(str[q]) == tempCount.end() && q > 0)
        {
            auto prev = tempCount.find(str[q - 1]);
            ans += to_string(prev->second) + prev->first;
            tempCount.clear();
        }
        tempCount[str[q]]++;
    }
    return ans;
}
string countAndSay(int num)
{
    string res = "1";
    for (int q = 1; q < num; q++)
    {
        res = generator(res);
    }
    return res;
}
int main() 
{
    int num;
    cout << "Enter the value of num: ";
    cin >> num;
    if (num <= 0)
    {
        cout << "Invalid input. Please enter a positive integer." << endl;
        return 0;
    }
    string result = countAndSay(num);
    cout << "The " << num << "-th term in the Count and Say sequence is: " << result << endl;
    return 0;
}

Output:

Enter the value of num: 5
The 5-th term in the Count and Say sequence is: 111221

Explanation:

The C++ code presented here is designed to generate the n-th term in the Look-and-Say sequence. Initially, the generateLookAndSay function is responsible for managing the cases where n is equal to 1 or 2, which result in the return of "1" and "11" respectively. In scenarios where n exceeds 2, the function proceeds to construct the sequence incrementally. Starting with "11", it evaluates consecutive groups of identical digits, computes their frequency, and then appends the count and digit to form the next term. By utilizing two strings - currentTerm to hold the current sequence and nextTerm to build the subsequent one - the process iterates until the desired term is achieved. Upon receiving an integer input n, the main function executes generateLookAndSay(n) and displays the generated sequence.

Method 3: Using dynamic programming

To prevent redundant computations and enhance effectiveness, the Look-and-Say series employs dynamic programming. This technique optimizes the process by saving all interim rows in a string vector. Through this strategy, each term is produced by tallying the sequential instances of individual characters from the preceding term, capitalizing on the sequence's self-referential nature. By assessing the i-th row and enumerating consecutive characters, the i+1-th row can be constructed, provided the i-th row is already available. This method minimizes time complexity by eliminating the need to recalculate previous rows repeatedly.

Follow the steps to implement the above approach:

• ✅ To store the intermediate results, initialize a vector of strings. As the first row of the Look-and-Say pattern, set the vector's first element to "1".
• ✅ Each row of the Look-and-Say pattern, from the second row (i = 1) to the nth row (i < n), is generated using a for loop.
• ✅ Create an empty string temporary for each loop to hold the subsequent Look-and-Say pattern row.
• ✅ The current row of the pattern is saved in the (i-1)-th element of the vector, and it can be iterated by using a for loop.
• ✅ Use a while loop inside the loop to count how many times the same character appears in the current row.
• ✅ Add the current character and the number of consecutive occurrences to the temporary string when the while loop is finished.
• ✅ Add the temporary string to the vector as the i-th element, signifying the subsequent row of the Look-and-Say pattern, once the inner loop is complete.
• ✅ Return the nth element of the vector, which includes the nth row of the Look-and-Say sequence, after the outer loop has finished.

Example:

Let's consider a sample to demonstrate the Look-and-Say Sequence in C++.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
string generateLookAndSaySequence(int term)
{
    vector<string> sequence(term + 1);
    sequence[1] = "1";
    for (int q = 2; q <= term; q++)
    {
        string previousTerm = sequence[q - 1];
        string currentTerm = "";
        for (int k = 0; k < previousTerm.size(); k++)
        {
            int repetitionCount = 1;
            while (k + 1 < previousTerm.size() && previousTerm[k] == previousTerm[k + 1])
            {
                repetitionCount++;
                k++;
            }
            currentTerm += to_string(repetitionCount) + previousTerm[k];
        }
        sequence[q] = currentTerm;
    }
    return sequence[term];
}
int main()
{
    int termNumber;
    cout << "Enter the term number for the Look-and-Say sequence: ";
    cin >> termNumber;
    cout << "The " << termNumber << "th term in the Look-and-Say sequence is: " << generateLookAndSaySequence(termNumber) << endl;
    return 0;
}

Output:

Enter the term number for the Look-and-Say sequence: 5
The 5th term in the Look-and-Say sequence is: 111221

Complexity Analysis:

• ✅ Time Complexity: O(n*m)
• ✅ Space complexity: O(n*m)

Explanation:

This C++ software produces the Look-and-Say series up to a word specified by the user. To retain interim expressions, the generateLookAndSaySequence function starts by setting up a string vector, with "1" representing the initial term. Each term is then formed by counting the consecutive identical characters in the preceding term, and combining the count with the character to generate the current term. This process continues until the specified term is generated. The primary function triggers the generateLookAndSaySequence function upon obtaining the term number from the user, and delivers the corresponding term within the series.

Method 4: Using Stacks

In this technique, the counting of successive occurrences of digits in the Look-and-Say sequence is performed using a stack data structure. Initially, the digit is added to the stack if it is empty. Subsequently, each new digit encountered is added to the stack to preserve the sequence if it matches the digit at the top of the stack. When a different digit is encountered, the top digit of the stack and the length of the stack (indicating the count of consecutive digits) are combined into a string (count + digit). Once the stack is emptied, the current digit is added to it to continue the processing. This method effectively monitors and manages consecutive digit groupings to generate the sequence.

Example:

Let's consider another instance to demonstrate the Look-and-Say Sequence in C++.

#include <bits/stdc++.h>
using namespace std;
string generateLookAndSay(int termNumber) 
{
    if (termNumber == 1) 
        return "1";
    string result = "";
    string previousTerm = generateLookAndSay(termNumber - 1);
    stack<char> digitStack;
    for (int index = 0; index <= previousTerm.length(); ++index)
    {
        if (index == previousTerm.length() || (!digitStack.empty() && digitStack.top() != previousTerm[index])) 
        {
            stringstream stream;
            string countAsString = "";
            stream << digitStack.size();
            stream >> countAsString;
            result += countAsString;
            result += digitStack.top();
            while (!digitStack.empty()) 
                digitStack.pop();
        }
        if (index != previousTerm.length()) 
            digitStack.push(previousTerm[index]);
    }
    return result;
}
int main()
{
    int termNumber;
    cout << "Enter the term number for the Look-and-Say sequence: ";
    cin >> termNumber;
    cout << "The " << termNumber << "th term in the Look-and-Say sequence is:"
    << generateLookAndSay(termNumber) << endl;
    return 0;
}

Output:

Enter the term number for the Look-and-Say sequence: 5
The 5th term in the Look-and-Say sequence is:111221

Complexity Analysis:

• ✅ Time complexity: O(kn)
• ✅ Auxiliary Space: O(kn)

Explanation:

The Look-and-Say sequence is produced iteratively through the following C++ code. The generateLookAndSay function iterates over each term by analyzing the previous term, identifying continuous identical digits using a stack, and then forming the output by adding the count and the digit. The primary function displays the corresponding sequence term upon input of a term number by the user.