I get inspiration from your solution. Here I just add additional variable: maxCount to avoid over-deep recursion.

class Solution {
public int longestSubstring(String s, int k) {
int n = s.length();
if (n==0) return 0;
int[] chars = new int[26];
for(int i=0; i<n; i++) chars[s.charAt(i)-'a']++;
// minCount to use evalute next recursion
// maxCount to avoid over-deep recursion
int minCount=n, maxCount=0;
char minChar = 'a';
for(int i=0; i<26; i++) {
if (chars[i]!=0&&minCount>chars[i]) {
minCount = chars[i];
minChar = (char)(i+'a');
}
if (maxCount<chars[i]) maxCount = chars[i];
}
if (minCount>=k) return n;
if (maxCount<k) return 0;
String[] arr = s.split(minChar+"");
int rec = 0;
for(String str: arr) {
rec = Math.max(rec, longestSubstring(str, k));
}
return rec;
}
}