# Time complexity of finding subsequences of a string segmented into parts

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.