Recursion Time Complexity (Half n' Half)
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.