Naive Java Solution18ms with sliding window technique.

• The worst case performance seems to be O(26n^2) but it runs faster than some O(26n) solutions. Is the reason weak test cases?

public class Solution {

``````public int longestSubstring(String s, int k) {
if(s.isEmpty()) return 0;
int ans = 0;
int a[][] = new int[s.length()][26];
a[0][s.charAt(0)-'a']++;
for(int i = 1;i<s.length();i++){
int ch = s.charAt(i)-'a';
for(int j = 0;j<ch;j++){
a[i][j] = a[i-1][j];
}
a[i][ch] = a[i-1][ch]+1;
for(int j = ch+1;j<26;j++){
a[i][j] = a[i-1][j];
}
}

int l = k;
int r = s.length();
for(int m =r;m>=l;m--){
if(isValid(k,a,s,m)) {
ans = m;
break;
}
}

return ans;
}

public boolean isValid(int k,int a[][], String s, int m){
for(int i = 0;i<=s.length()-m;i++){
boolean ok =  true;
for(int j = 0;j<26;j++){
int num  = (i==0)?a[i+m-1][j]:a[i+m-1][j]-a[i-1][j];
if(num!=0 && num<k){
ok =  false;
break;
}
}
if(ok) return true;
}
return false;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.