Java 53 ms, O(N) time, O(N) space solution

• ``````
public class Solution {
// interval overlapping algorithm, or frog jumpping algorithm
private int lastlen(List<List<Integer>> lists, int k){

int start = -1;
Set<Integer> set = new HashSet<>();
for(int i = 0; i < lists.size(); i++) {
List<Integer> list = lists.get(i);
if (list != null && list.size() < k) {
start = Math.max(start, list.get(list.size() - 1));
}else if(list != null){
}
}

boolean exists = true;
while(exists){
exists = false;
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
List<Integer> list = lists.get(it.next());
int size = list.size();
if(list.get(size - k) < start){
start = Math.max(start, list.get(size - 1));
exists = true;
it.remove();
}
}
}

return start;
}

public int longestSubstring(String s, int k){

int res = 0;
List<List<Integer>> indices = new ArrayList<>();
for(int i = 0; i < 26; i++){
}
for(int i = 0; i < s.length(); i++){
int ind = (int)(s.charAt(i) - 'a');
if(indices.get(ind) == null)
indices.set(ind, new ArrayList<Integer>());
res = Math.max(i - lastlen(indices, k), res);
}

return res;

}
``````

• A somewhat optimized version:

``````public class Solution {

private int lastlen(Map<Character, Deque<Integer>> lists, int k){

int start = -1;
Set<Character> set = new HashSet<>();
for(Character c : lists.keySet()) {
Deque<Integer> list = lists.get(c);
if (list != null && list.size() < k) {
start = Math.max(start, list.getLast());
}else{
while(list.size() > k){
list.remove();
}
}
}

boolean exists = true;
while(exists){
exists = false;
Iterator<Character> it = set.iterator();
while(it.hasNext()){
Deque<Integer> list = lists.get(it.next());
int size = list.size();
if(list.peekFirst() < start){
start = Math.max(start, list.peekLast());
exists = true;
it.remove();
}
}
}

return start;
}

public int longestSubstring(String s, int k){

int res = 0;
Integer start = null;
Map<Character, Deque<Integer>> indices = new HashMap<>();
for(int i = 0; i < s.length(); i++){
Character c = s.charAt(i);
Deque<Integer> q = indices.get(c);
if(q == null)
indices.put(c, q=new ArrayDeque<Integer>());
q.offer(i);
if(start != null && q.size() >= k && q.getFirst() > start);
else{
start = lastlen(indices, k);
}
res = Math.max(i - start, res);
}

return res;

}
}
``````

• Also a binary search algorithm, len = s.length()/2, check whether some substring with len satisfies the condition, if not, then len = s.length()/4; if so, len = 0.75*s.length();

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