1
$\begingroup$

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:

  • Input: string $s = s_1,\ldots,s_n$, integer $k$
  • Go over all symbols $s_1,\ldots,s_n$, one by one
  • For each symbol $s_i$, check whether it appears less than $k$ times in $s$
  • If all symbols appeared at least $k$ times, return $n$
  • Otherwise, let $i$ be the first index such that $s_i$ appears less than $k$ times
  • Call the procedure recursively on $s_1,\ldots,s_{i-1}$ and on $s_{i+1},\ldots,s_n$, and output the maximum

Here is a C++ implementation:

int longestSubstring(string s, int k) {
        for (int i = 0; i < s.length(); i++) {
            if (count(s.begin(), s.end(), s[i]) < k) { 
                string left = s.substr(0,i);
                string right = s.substr(i+1,s.size()-1);
                return max(longestSubstring(left,k),longestSubstring(right,k));
            }
        }
        return s.length();     
    }

The count method runs in $O(n)$.

I'm new to asymptotic complexity, but from what I understand, "half n' half" recursion has time $T(n) = 2T(n/2)+f(n)$ where $f(n)$ is the time the rest of the execution takes. At this point, we'd induct, and get a general pattern. Then, given that we usually know $T(0)$ and $T(1)$, we can get an expression in $n$, which would be our time complexity.

Now, my problem is that my implementation doesn't split the string into exact halves (in the same way a BST traversal splits the input in halves, for example), so I can't really write $T(n/2)$, correct? Are $T(0)$ and $T(1)$, $O(1)$ and $O(n)$ respectively?

Is there, perhaps, a faster way to solve this problem? Leetcode says it runs in 0ms, but I find that dubious. It takes a longer time to execute than one of the highest upvoted Python implementations, which is supposedly $O(n)$.

$\endgroup$
  • $\begingroup$ Even when the answer is $n$, your solution runs in time $\Omega(n^2)$. Note, however, that you can check whether all letters appear at least $k$ times in $O(n)$, since the alphabet is known in advance (it's the lowercase letters); and even for an arbitrary alphabet, you could sort the array and so check the condition in time $O(n\log n)$. $\endgroup$ – Yuval Filmus Jul 17 at 1:35
  • $\begingroup$ When leetcode says it runs in 0ms, it is rounding down some other quantity. The running time is strictly positive, but less than half a millisecond. $\endgroup$ – Yuval Filmus Jul 17 at 2:09
  • $\begingroup$ Can you help me understand why its $\Omega(n^2)$? That would just be the time complexity of the for loop and its nested "count" function, no? Recursion doesn't play a role? $\endgroup$ – alwaysiamcaesar Jul 17 at 4:14
  • $\begingroup$ Right, that’s when there is no recursion. $\endgroup$ – Yuval Filmus Jul 17 at 4:14
  • $\begingroup$ Oh, right, best case. I understand. But then, what would be the worst case (Big O)? I realy want to know how to deal with the recursion. $\endgroup$ – alwaysiamcaesar Jul 17 at 4:18
0
$\begingroup$

I can offer one simple optimizations to your code.

At the moment your code will take $\Omega(n^2)$ time even on a string in which each symbol appears at least $k$ times. This can be avoided using counting sort: using a single pass, you can compute how many times each letter appears. If every letter appears either 0 or at least $k$ times, then the current string is good. This takes linear time.

(This uses the fact that it is known that all letters of the string are lowercase letters. If the letters are arbitrary, you can still speed this up by sorting the array.)

Even after this optimization, your code suffers from a problem. Suppose that $k = n/2 + 1$, and let the string consist of $n/2$ copies of a followed by $n/2$ copies of b (as an aside, you can immediately return 0 in this case – a further optimization). Your code will recurse on the substring $s_2,\ldots,s_n$, the on the substring $s_3,\ldots,s_n$, and so on, not giving up at any point. Therefore it will take time $\Theta(n^2)$ (or, without the first optimization mentioned above, $\Theta(n^3)$).

In order to avoid this, suppose that you found out that $s_i$ appears fewer than $k$ times. Find all occurrences of $s_i$, partition the string accordingly, and recurse on each such substring. This will guarantee that each substring won't have the letter $s_i$. Each time you recurse, you have one fewer letter appearing, and so the depth of the recursion tree is at most 26. Therefore the algorithm will run in linear time.

$\endgroup$
  • $\begingroup$ You can also apparently solve it using a sliding window. This might be more efficient, especially with a larger alphabet. $\endgroup$ – Yuval Filmus Jul 17 at 2:11
  • $\begingroup$ I wonder, can we do $O(n + |\Sigma|)$ or $O(n \cdot \log |\Sigma|)$ instead of $O(|\Sigma|n)$? $\endgroup$ – orlp Jul 17 at 2:12
  • $\begingroup$ This solution is actually $O(|\Sigma|^2 n)$. $\endgroup$ – Yuval Filmus Jul 17 at 2:13
  • $\begingroup$ Ah, definitely makes looking for a better answer attractive then. $\endgroup$ – orlp Jul 17 at 2:14

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.