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
To understand the problem, here are some examples:
1. Count and Say: Observations & Logic
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
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] += 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.
May 11, 2022