Count and Say. Or may be Not!

Question: 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.

You may check the last two posts (post 1, post 2) for a more sane solution. But if you would like a little humor (yep, you read it right!), read on…

Approach: Oh thee brave soul, who chooseth to charge ahead!

Here is the thing — this solution leverages on certain constraints set in the question.

• Starting from where we had left off in the previous post. We had used a map to store the pattern values as and when we generated them for future use. In short we need a lookup, simply because, these patterns are constant.
• Thankfully, the question also mentions that the maximum value of “n” for which the pattern needs to be generated is for n=30.

I hope you see where I am headed. Yes! I did it. I created a map and stored all the patterns for n=1 to 30.

class Solution {
public String countAndSay(int n) {
        HashMap<Integer, String> map = new HashMap<>();
        map.put(1,"1");
        map.put(2,"11");
        ...
        //Trust me you really don't want me to skip these ellipsis
        map.put(30,"311311...2211");
        return map.get(n);
    }
}

Well, let’s step back and evaluate this code. Now, if you want to call the method countAndSay() to get the pattern for 5, this code will end up creating a ginormous map with all possible values. And, to make this worse, this code ends up doing this every single time the method is called.

The work around for this problem is to make sure that the map is initialized and constructed only once and is maintained and shared across all calls and instances. Exactly like a lookup table.

To do so, we take the help of the modifier — “static”. We make the map as a static variable shared across all instances and method calls. Also, we construct the map in a static anonymous code block, once again to ensure that the same purpose of “create-once-use-many-times”.

//Approach 3:
//Runtime: 0ms (this is NOT a typo)
//Memory usage: 35.5MB
class Solution {
    static HashMap<Integer, String> map = new HashMap<>();
    static {
       map.put(1,"1");
       ...
       map.put(30,"311311...2211");
    }
    public String countAndSay(int n) {
     return map.get(n);
    }
    
}

After submitting the code, I debated if this is a good enough solution to be shared here. It’s a witty solution no doubt.

Often I try to fashion some of the most complicated solutions just because the obvious approach seems too mundane. This episode reminded me to step back and evaluate the context/requirement before polluting the IDE.

(P.S: I’m of course, NOT advocating this solution to be a good one. But, do take the time to enjoy the humor.:P )

Find more posts here.

Cheers & Chao!