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)$.

  • $\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$ Jul 17, 2019 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$ Jul 17, 2019 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$ Jul 17, 2019 at 4:14
  • $\begingroup$ Right, that’s when there is no recursion. $\endgroup$ Jul 17, 2019 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$ Jul 17, 2019 at 4:18

2 Answers 2


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.

  • $\begingroup$ You can also apparently solve it using a sliding window. This might be more efficient, especially with a larger alphabet. $\endgroup$ Jul 17, 2019 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, 2019 at 2:12
  • $\begingroup$ This solution is actually $O(|\Sigma|^2 n)$. $\endgroup$ Jul 17, 2019 at 2:13
  • $\begingroup$ Ah, definitely makes looking for a better answer attractive then. $\endgroup$
    – orlp
    Jul 17, 2019 at 2:14
  • $\begingroup$ There is a strange constraint in the problem statement: $k$ can be larger than the string length !? $\endgroup$
    – user16034
    Nov 28, 2022 at 12:48

Starting from the leftmost position, maintain a histogram of the symbol frequencies. All entries initially zero. Every time you process a symbol, check if it is a new one (frequency still zero), and increment a count of "lacunary" symbols in the string; also increment the frequency for this symbol and if it reaches exactly $k$, decrement the count of lacunary symbols. Then keep the value of the length of the last string with zero lacunarity, which is perforce the longest. This process takes linear time in the length of the string (plus the size of the alphabet).

Then repeat the whole process, starting from the second symbol, and so on. So far I see no way to make it faster.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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