Look And Say or Count And Say Sequence

$\mathtt{REFERENCE}$ @ LeetCode

This is a LeetCode Problem. You can find it HERE

Problem Definition

This problem is actually generation of $look-and-say\ sequence$. DESCRIPTION

The count-and-say sequence is the sequence of integers with the first five terms as following:

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221
 
 1 is read off as "one 1" or 11.
 11 is read off as "two 1s" or 21.
 21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.
  

Solution

Then $nth$ sequence is generated using $(n-1)th$ sequence. So the obvious solution would to go on generating sequences starting from $n=1$ for which the $sequence = 1$.

Algorithm to generate a sequence from previous sequence is simple.

1. Traverse through previous sequence character by character.
1. Maintian the count of repeated character.
2. When a new character is encountered, append to result the $count$ and the $character$.
2. Return result.

We will have to repeat this algorithm until the required sequence is generated.

P.S. When I was tyring to solve this problem, I was looking for more efficient solution. More specifially I was looking for a pattern so that I could directly generate the $nth$ sequence without computing the intermediate sequences. As it turns out, there is no such solution. So the process described above is the actual solution to this problem.

Implementation

Following is the implementation in $GoLang$.

Important thing to keep in mind during the implementation is the generation of intermediate strings. Be careful to generate intermediate and final sequence in $\cal{O(n)}$ time.

	func countAndSay(n int) string {
	prev := "1"
	if n == 1 {
	return prev
	}
	for i := 2; i <= n; i++ {
	prev = compute(prev)
	}
	return prev
	}
	func compute(term string) string {
	var sb strings.Builder
	prev := rune(term[0])
	var count int = 0
	for _, v := range term {
	if v == prev {
	count++
	} else {
	fmt.Fprintf(&sb, "%d", count)
	sb.WriteRune(prev)
	prev = v
	count = 1
	}
	}
	fmt.Fprintf(&sb, "%d", count)
	sb.WriteRune(prev)
	return sb.String()
	}

view raw look-and-say.go hosted with ❤ by GitHub

Complexity

Method countAndSay() runs for $\cal{O(n)}$ time $n$ being the $nth$ sequence number.

Method compute() which computes current sequence using previous sequence, runs for $\cal{O(m)}$ time where $m$ is number of characters in previous sequence.

Assuming $m=n$, The Time Complexity of this solution will be $\cal{O(n^2)}$.

---

---

---