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.
