1
$\begingroup$

Let $S$ be a string of length $N$, consisting of digits 0 to 9. For convenience, we assume $N$ to be a multiple of 3.

Then, we split $S$ into $N/3$ equal parts, each of length 3.

For each equal part, we count/enumerate all subsequences of all lengths up to 3.

Finally, we total up how many such subsequences are there altogether.

What is the time complexity of the above algorithm? Thanks.

I give a more concrete example in case the above is not clear. Suppose $S=`111211'$, of length 6.

We first split it into 2 parts $`111'$ and $`211'$. For the first part $`111'$, we count that there are 3 subsequences of $`11'$ (note that subsequences do not have to be consecutive unlike substrings), for the $`211'$, there is 1 subsequence of $`11'$, so in total there are 4 subsequences of $`11'$. We do this for all possible subsequences up to length 3, even for subsequences that do not appear such as $'000'$, we count that it occurs zero times.


I am new to time complexity, but I did try to calculate it myself. For each part of length 3, the time complexity of enumerating the subsequences is $O(1)$? Hence, in total, we have to repeat it $N/3$ times, so the overall time complexity is $O(N)$? Is that correct? Thanks a lot.

$\endgroup$
2
$\begingroup$

Yes, your analysis is correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.