Number of c's with an a before and without b between, and number of d's with an a after and without b between X17557
The input of this exercise is a sequence of characters over
{a,b,c,d}. We want to count two things:
We want to count the number of
c’s satisfying the following: before thiscthere is at least onea. Moreover, if we consider the closestato thiscand before thisc, then, between both letters there is nob. For example, in the following word we have boldfaced thec’s that must be counted:cdbdadccbdcacbbdcdabcd.We want to count the number of
d’s satisfying the following: after thisdthere is at least onea. Moreover, if we consider the closestato thisdand after thisd, then, between both letters there is nob. For example, in the following word we have boldfaced thed’s that must be counted:cdbdadccbdcacbbdcdabcd.
Input
The input is a sequence of characters over
{a,b,c,d}, in just one line.
Output
The output has two natural numbers, in one line, and separated by a white space:
the number of
c’s that have anabefore and nobbetween them.the number of
d’s that have anaafter and nobbetween them.
Observation
It is not allowed to use any massive storage data structure, not even
string. Read and treat the input character by
character.
Assessment over 10 points:
Slow solution: 5 points.
Fast solution: 10 points.
We understand as fast solution one being correct, with linear cost and able to overcome both the public and private tests. We understand as slow solution one not being fast, but correct and able to overcome the public tests.
Input
cdbdadccbdcacbbdcdadacacadbcd
Output
5 5
Input
bbabddccdcdcddddcdcadccbddcabbbbaaaccdcdccdddcaadcdcccdcaaddcdcdddccddcbbaadddcacdddcddbacdcccaccbabdcbddcdcdddcdcdcdcbdddcddbabcacddccddcdccccc
Output
36 23