Find the n’th term in Look-and-say (Or Count and Say) Sequence. The look-and-say sequence is the sequence of the below integers:
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, …
How is the above sequence generated?
n’th term is generated by reading (n-1)’th term.
The first term is "1"
Second term is "11", generated by reading first term as "One 1"
(There is one 1 in previous term)
Third term is "21", generated by reading second term as "Two 1"
Fourth term is "1211", generated by reading third term as "One 2 One 1"
and so on
How to find n’th term?
Example:
Input: n = 3
Output: 21
Input: n = 5
Output: 111221
The idea is simple, we generate all terms from 1 to n. First, two terms are initialized as “1” and “11”, and all other terms are generated using previous terms. To generate a term using the previous term, we scan the previous term. While scanning a term, we simply keep track of the count of all consecutive characters. For a sequence of the same characters, we append the count followed by the character to generate the next term.
Below is an implementation of the above idea.
C++
#include <bits/stdc++.h>
using namespace std;
string countnndSay( int n)
{
if (n == 1) return "1" ;
if (n == 2) return "11" ;
string str = "11" ;
for ( int i = 3; i<=n; i++)
{
str += '$' ;
int len = str.length();
int cnt = 1;
string tmp = "" ;
for ( int j = 1; j < len; j++)
{
if (str[j] != str[j-1])
{
tmp += cnt + '0' ;
tmp += str[j-1];
cnt = 1;
}
else cnt++;
}
str = tmp;
}
return str;
}
int main()
{
int N = 3;
cout << countnndSay(N) << endl;
return 0;
}
|
Java
class GFG
{
static String countnndSay( int n)
{
if (n == 1 ) return "1" ;
if (n == 2 ) return "11" ;
String str = "11" ;
for ( int i = 3 ; i <= n; i++)
{
str += '$' ;
int len = str.length();
int cnt = 1 ;
String tmp = "" ;
char []arr = str.toCharArray();
for ( int j = 1 ; j < len; j++)
{
if (arr[j] != arr[j - 1 ])
{
tmp += cnt + 0 ;
tmp += arr[j - 1 ];
cnt = 1 ;
}
else cnt++;
}
str = tmp;
}
return str;
}
public static void main(String[] args)
{
int N = 3 ;
System.out.println(countnndSay(N));
}
}
|
Python3
def countnndSay(n):
if (n = = 1 ):
return "1"
if (n = = 2 ):
return "11"
s = "11"
for i in range ( 3 , n + 1 ):
s + = '$'
l = len (s)
cnt = 1
tmp = ""
for j in range ( 1 , l):
if (s[j] ! = s[j - 1 ]):
tmp + = str (cnt + 0 )
tmp + = s[j - 1 ]
cnt = 1
else :
cnt + = 1
s = tmp
return s;
N = 3
print (countnndSay(N))
|
C#
using System;
class GFG
{
static string countnndSay( int n)
{
if (n == 1) return "1" ;
if (n == 2) return "11" ;
string str = "11" ;
for ( int i = 3; i <= n; i++)
{
str += '$' ;
int len = str.Length;
int cnt = 1;
string tmp = "" ;
char []arr = str.ToCharArray();
for ( int j = 1; j < len; j++)
{
if (arr[j] != arr[j - 1])
{
tmp += cnt + 0;
tmp += arr[j - 1];
cnt = 1;
}
else cnt++;
}
str = tmp;
}
return str;
}
public static void Main()
{
int N = 3;
Console.Write(countnndSay(N));
}
}
|
Javascript
<script>
function countnndSay(n)
{
if (n == 1)
return "1" ;
if (n == 2)
return "11" ;
let str = "11" ;
for (let i = 3; i <= n; i++)
{
str += '$ ';
let len = str.length;
// Initialize count
// of matching chars
let cnt = 1;
// Initialize i' th
let tmp = "" ;
let arr = str.split( "" );
for (let j = 1; j < len; j++)
{
if (arr[j] != arr[j - 1])
{
tmp += cnt + 0;
tmp += arr[j - 1];
cnt = 1;
}
else cnt++;
}
str = tmp;
}
return str;
}
let N = 3;
document.write(countnndSay(N));
</script>
|
PHP
<?php
function countnndSay( $n )
{
if ( $n == 1)
return "1" ;
if ( $n == 2)
return "11" ;
$str = "11" ;
for ( $i = 3;
$i <= $n ; $i ++)
{
$str = $str . '$' ;
$len = strlen ( $str );
$cnt = 1;
$tmp = "" ;
for ( $j = 1; $j < $len ; $j ++)
{
if ( $str [ $j ] != $str [ $j - 1])
{
$tmp = $tmp . $cnt + 0;
$tmp = $tmp . $str [ $j - 1];
$cnt = 1;
}
else $cnt ++;
}
$str = $tmp ;
}
return $str ;
}
$N = 3;
echo countnndSay( $N );
return 0;
?>
|
Time Complexity : O(n2)
Auxiliary Space : O(1)
Another Approach(Using STL): There is one more idea where we can use unordered_map from c++ stl to track the count of digits. Basic idea is to use a generator function that will generate a string from the previous string. In the count and say function we will iterate over integers from 1 to n-1 and keep updating our result.
C++
#include <bits/stdc++.h>
using namespace std;
string generator(string str)
{
string ans = "" ;
unordered_map< char , int >
tempCount;
for ( int i = 0; i < str.length() + 1; i++) {
if (tempCount.find(str[i]) == tempCount.end()
&& i > 0) {
auto prev = tempCount.find(str[i - 1]);
ans += to_string(prev->second) + prev->first;
tempCount.clear();
}
tempCount[str[i]]++;
}
return ans;
}
string countnndSay( int n)
{
string res = "1" ;
for ( int i = 1; i < n; i++) {
res = generator(res);
}
return res;
}
int main()
{
int N = 3;
cout << countnndSay(N) << endl;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static String generator(String str)
{
String ans = "" ;
HashMap<Character, Integer>tempCount = new HashMap<>();
for ( int i = 0 ; i < str.length() + 1 ; i++) {
if (i == str.length() || tempCount.containsKey(str.charAt(i)) == false && i > 0 ) {
ans += String.valueOf(tempCount.get(str.charAt(i- 1 ))) + str.charAt(i- 1 );
tempCount.clear();
}
if (i == str.length()){
tempCount.put( null , 1 );
}
else {
if (tempCount.containsKey(str.charAt(i))){
tempCount.put(str.charAt(i), tempCount.get(str.charAt(i))+ 1 );
}
else {
if (i != str.length())tempCount.put(str.charAt(i), 1 );
}
}
}
return ans;
}
static String countnndSay( int n)
{
String res = "1" ;
for ( int i = 1 ; i < n; i++) {
res = generator(res);
}
return res;
}
public static void main(String args[])
{
int N = 3 ;
System.out.println(countnndSay(N));
}
}
|
Python3
def generator(s):
ans = ""
tempCount = {}
for i in range ( len (s) + 1 ):
if i = = len (s) or s[i] not in tempCount and i > 0 :
ans + = str (tempCount[s[i - 1 ]]) + s[i - 1 ]
tempCount.clear()
if i = = len (s):
tempCount[ None ] = 1
else :
if s[i] in tempCount:
tempCount[s[i]] + = 1
else :
tempCount[s[i]] = 1
return ans
def countAndSay(n):
res = "1"
for i in range ( 1 , n):
res = generator(res)
return res
N = 3
print (countAndSay(N))
|
C#
using System;
using System.Collections.Generic;
class GFG {
static string generator( string str)
{
string ans = "" ;
Dictionary< char , int > tempCount = new Dictionary< char , int >();
for ( int i = 0; i < str.Length + 1; i++) {
if (i == str.Length || !tempCount.ContainsKey(str[i]) && i > 0) {
ans += tempCount[str[i - 1]].ToString() + str[i - 1];
tempCount.Clear();
}
if (i == str.Length){
tempCount.Add( '\0' , 1);
}
else {
if (tempCount.ContainsKey(str[i])){
tempCount[str[i]]++;
}
else {
if (i != str.Length)tempCount.Add(str[i], 1);
}
}
}
return ans;
}
static string countnndSay( int n)
{
string res = "1" ;
for ( int i = 1; i < n; i++) {
res = generator(res);
}
return res;
}
public static void Main()
{
int N = 3;
Console.WriteLine(countnndSay(N));
}
}
|
Javascript
function generator(str) {
let ans = "" ;
let tempCount = new Map();
for (let i = 0; i < str.length + 1; i++) {
if (!tempCount.has(str[i]) && i > 0) {
const prev = tempCount.get(str[i - 1]);
ans += prev + str[i - 1];
tempCount.clear();
}
tempCount.set(str[i], (tempCount.get(str[i]) || 0) + 1);
}
return ans;
}
function countAndSay(n) {
let res = "1" ;
for (let i = 1; i < n; i++) {
res = generator(res);
}
return res;
}
const N = 3;
console.log(countAndSay(N));
|
Thanks to Utkarsh and Neeraj for suggesting the above solution.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above
Using dynamic programming:
The idea behind the dynamic programming solution to this problem is to generate each row of the look-and-say pattern based on the previous row, and store all the intermediate results in a vector of strings. By doing this, we avoid repeating the same calculations for multiple rows and reduce the overall time complexity of the solution.
The intuition behind this approach is that the look-and-say pattern is self-referential, meaning that each row can be generated from the previous row by counting the consecutive occurrences of each character. Therefore, if we have the ‘i’th row of the look-and-say pattern, we can generate the ‘i+1’th row by counting the consecutive occurrences of each character in the ‘i’th row.
Follow the steps to implement the above approach:
1. Initialize a vector of strings to store the intermediate results. Set the first element of the vector to “1”, which represents the first row of the look-and-say pattern.
2. Use a for loop to generate each row of the look-and-say pattern, starting from the second row (i = 1) up to the nth row (i < n).
3. For each iteration of the loop, initialize an empty string temp to store the next row of the look-and-say pattern.
4. Use a for loop to iterate through the current row of the look-and-say pattern, stored in the i-1th element of the vector.
5. Within the inner for loop, use a while loop to count the number of consecutive occurrences of the same character.
6. After the while loop, append the count of consecutive occurrences and the current character to the temp string.
7. After the inner for loop, add the temp string to the vector of strings as the ith element, which represents the next row of the look-and-say pattern.
8. After the outer for loop, return the nth element of the vector of strings, which represents the nth row of the look-and-say pattern
Below is the implementation of the above approach
C++
#include <iostream>
#include <vector>
using namespace std;
string generateNthRow( int n)
{
vector<string> dp(n + 1);
dp[1] = "1" ;
for ( int i = 2; i <= n; i++) {
string prev = dp[i - 1];
string curr = "" ;
for ( int j = 0; j < prev.size(); j++) {
int count = 1;
while (j + 1 < prev.size()
&& prev[j] == prev[j + 1]) {
count++;
j++;
}
curr += to_string(count) + prev[j];
}
dp[i] = curr;
}
return dp[n];
}
int main()
{
int n = 3;
cout << generateNthRow(n) << endl;
return 0;
}
|
Java
import java.util.*;
public class Main {
public static String generateNthRow( int n)
{
List<String> dp = new ArrayList<>(n + 1 );
dp.add( "1" );
for ( int i = 2 ; i <= n; i++) {
String prev = dp.get(i - 1 - 1 );
String curr = "" ;
for ( int j = 0 ; j < prev.length(); j++) {
int count = 1 ;
while (j + 1 < prev.length() && prev.charAt(j) == prev.charAt(j + 1 )) {
count++;
j++;
}
curr += Integer.toString(count) + prev.charAt(j);
}
dp.add(curr);
}
return dp.get(n - 1 );
}
public static void main(String[] args) {
int n = 3 ;
System.out.println(generateNthRow(n));
}
}
|
Python3
def generateNthRow(n):
dp = [''] * (n + 1 )
dp[ 1 ] = '1'
for i in range ( 2 , n + 1 ):
prev = dp[i - 1 ]
curr = ''
j = 0
while j < len (prev):
count = 1
while j + 1 < len (prev) and prev[j] = = prev[j + 1 ]:
count + = 1
j + = 1
curr + = str (count) + prev[j]
j + = 1
dp[i] = curr
return dp[n]
n = 3
print (generateNthRow(n))
|
C#
using System;
using System.Collections.Generic;
public class Program
{
public static string GenerateNthRow( int n)
{
List< string > dp = new List< string >(n + 1);
dp.Add( "1" );
for ( int i = 2; i <= n; i++)
{
string prev = dp[i - 1 - 1];
string curr = "" ;
for ( int j = 0; j < prev.Length; j++)
{
int count = 1;
while (j + 1 < prev.Length && prev[j] == prev[j + 1])
{
count++;
j++;
}
curr += count.ToString() + prev[j];
}
dp.Add(curr);
}
return dp[n - 1];
}
public static void Main( string [] args)
{
int n = 3;
Console.WriteLine(GenerateNthRow(n));
}
}
|
Javascript
function generateNthRow(n) {
let dp = [ "1" ];
for (let i = 2; i <= n; i++) {
let prev = dp[i - 1 - 1];
let curr = "" ;
for (let j = 0; j < prev.length; j++) {
let count = 1;
while (j + 1 < prev.length && prev.charAt(j) == prev.charAt(j + 1)) {
count++;
j++;
}
curr += count.toString() + prev.charAt(j);
}
dp.push(curr);
}
return dp[n - 1];
}
let n = 3;
console.log(generateNthRow(n));
|
Explanation of the above code: here we are using a vector of strings dp to store the generated rows of the look-and-say pattern. We initialize the first element of the dp vector with the string “1”.
In the for loop, we iterate from the 2nd row to the nth row and generate each row based on the previous row. We use a nested for loop to iterate over each character of the previous row. The outer for loop keeps track of the current character, and the inner while loop counts the number of consecutive occurrences of the same character. After counting the number of occurrences, we add the count and the current character to the curr string, which represents the current row of the look-and-say pattern. Finally, we update the dp[i] with the curr string.
After the loop, we return the nth row stored in dp[n]
Time Complexity :O(n*m) where n is the number of rows to generate, and m is the maximum length of a row in the look-and-say pattern.
space complexity : O(n * m), where n is the number of rows to generate and m is the maximum length of a row in the look-and-say pattern.
Another Approach(Using Stacks):
Intuition:
the problem is simpler if we understand it as just feeding the output of the counting function into itself n times.
f(1) => 11 // base case
f(11) => 21
f(21) => 1211
f(1211) => 111221
.
.
.
n times
each time we are passing a number into the function we are just counting the number of same digits in a sequence and replacing the digit with the count and the digit
eg 33333 -> there are 5 threes so we return 53(count + digit)
Approach:
we use a stack to count the digits.
if the stack is empty we push to the stack
if the current digit is same as the digit on the top of the stack then we push to the stach.
if the current digit is not the same then we get the length of the stack and the digit in top of the stack return the len + digit as a string, empty the stack and push the current element to the top of the stack
we do this n times. each time the output of the function will be the input to the next iteration.
C++
#include <bits/stdc++.h>
using namespace std;
string countAndSay( int n)
{
if (n == 1)
return "1" ;
std::string ret{ "" };
std::string strToCount{ countAndSay(
n - 1) };
std::stack< char > stack;
for ( int i{ 0 }; i <= strToCount.length(); ++i) {
if (i == strToCount.length()
|| !stack.empty()
&& stack.top() != strToCount[i]) {
std::stringstream ss;
std::string toAdd{ "" };
ss << stack.size();
ss >> toAdd;
ret += toAdd;
ret += stack.top();
while (!stack.empty())
stack.pop();
}
if (i != strToCount.length())
stack.push(strToCount[i]);
}
return ret;
}
int main()
{
int n = 3;
cout << countAndSay(n) << endl;
return 0;
}
|
Java
import java.io.*;
import java.util.Stack;
public class GFG{
public static String countAndSay( int n) {
if (n == 1 )
return "1" ;
String strToCount = countAndSay(n - 1 );
StringBuilder ret = new StringBuilder();
Stack<Character> stack = new Stack<>();
for ( int i = 0 ; i <= strToCount.length(); ++i) {
if (i == strToCount.length() || (!stack.empty() && stack.peek() != strToCount.charAt(i))) {
ret.append(stack.size()).append(stack.peek());
stack.clear();
}
if (i != strToCount.length())
stack.push(strToCount.charAt(i));
}
return ret.toString();
}
public static void main(String[] args) {
int n = 3 ;
System.out.println(countAndSay(n));
}
}
|
Python3
def count_and_say(n):
if n = = 1 :
return "1"
ret = ""
str_to_count = count_and_say(n - 1 )
stack = []
for i in range ( len (str_to_count) + 1 ):
if i = = len (str_to_count) or (stack and stack[ - 1 ] ! = str_to_count[i]):
to_add = str ( len (stack)) + stack[ - 1 ]
ret + = to_add
stack.clear()
if i ! = len (str_to_count):
stack.append(str_to_count[i])
return ret
def main():
n = 3
print (count_and_say(n))
if __name__ = = "__main__" :
main()
|
C#
using System;
using System.Collections.Generic;
namespace CountAndSay
{
class Program
{
static string CountAndSay( int n)
{
if (n == 1)
return "1" ;
string ret = "" ;
string strToCount = CountAndSay(n - 1);
Stack< char > stack = new Stack< char >();
for ( int i = 0; i <= strToCount.Length; ++i)
{
if (i == strToCount.Length || (stack.Count > 0 && stack.Peek() != strToCount[i]))
{
ret += stack.Count.ToString() + stack.Peek();
stack.Clear();
}
if (i != strToCount.Length)
stack.Push(strToCount[i]);
}
return ret;
}
static void Main( string [] args)
{
int n = 3;
Console.WriteLine(CountAndSay(n));
}
}
}
|
Javascript
function countAndSay(n) {
if (n === 1)
return "1" ;
let strToCount = countAndSay(n - 1);
let ret = "" ;
let stack = [];
for (let i = 0; i <= strToCount.length; ++i) {
if (i === strToCount.length || (stack.length !== 0 && stack[stack.length - 1] !== strToCount[i])) {
ret += stack.length + stack[stack.length - 1];
stack = [];
}
if (i !== strToCount.length)
stack.push(strToCount[i]);
}
return ret;
}
let n = 3;
console.log(countAndSay(n));
|
Time complexity: O(kn),since we are calling the function n times and for k length of the string
Auxiliary Space: O(kn),stack space needed.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!