Author: Praveen Dhinwa
Editorialist: Bhuvnesh Jain
You are given an array consisting of ‘C’, ‘E’ and ‘S’ denoting cooking, eating and sleeping respectively. You need to tell whether the array is correct i.e. has ‘C’, ‘E’ and ‘S’ in correct order or not.
The problem can be solved as stated in the question itself. All we need to find is whether is the activities recorded by Chef’s dog are in the order Cooking, Eating and Sleeping or not. So, we can group the equal elements together. This can be done easily using a “for” loop as follows:
vector u; for i in 0 to s.length()-1: j = i while(j < s.length() && s*==s[j]): j += 1 u.push_back(s*); i = j-1
Now, if size(u) > 3, then answer is definitely “no”. Otherwise, check if it follows the sequence. i.e.
if size(u) == 3, u = 'C', u = 'E', u = 'S' if size(u) == 2, u = 'C', u = 'S' or u = 'C', u = 'E' or u = 'E', u = 'S' if size(u) == 1, trivally true
The above will suffice for 100 points as the complexity of the above code is O(n). It may initially seem that the complexity of the above code is O(n^2). To see why the above doesn’t hold, let us analyze the complexity in a different manner. We see how many time each position will be visited. Each position will be visited once, either by the variable i or j. Since there are n locations in total, the complexity becomes O(n).
The question can be solved using information about the state only. Let us denote the states ‘C’, ‘E’, ‘S’ by 0, 1, 2 respectively. Then the solution is “yes” if and only if, state* <= state[i+1] for 0 <= i < s.length()-1. The editorialist has used this idea and the implementation can be seen in his solution.
This solution is similar to the second one except that instead of maintaining the state, we just check if the given string corresponding to the required regular expression or not. This is also a builtin function in most languages as well.
For example, the C++ code would be
cout << (regex_match(s, regex("^CES*$")) ? “yes” : “no”) << endl;
The java code code be found in the answer below.
O(n) per test case