# Java Solution with Array, HashMap and Math tricks

• ``````public boolean findStart = false;
public int start = 0;
public int end = 0;
public int longestSubstring(String s, int k) {
int result = 0;
int[] a = new int[s.length()];
int[] b = new int[s.length()];
int[] c = new int[s.length()];

int[] memA = new int[256];
for(int i = 0; i < a.length; i++){
memA[s.charAt(i)]++;
a[i] = memA[s.charAt(i)];
}

int[] memB = new int[256];
for(int i = b.length - 1; i >= 0; i--){
memB[s.charAt(i)]++;
b[i] = memB[s.charAt(i)];
}

for(int i = 0; i < a.length; i++){
c[i] = a[i] + b[i];
}
//build c array

for(int i = 0; i < c.length; i++){
//if c[i] is qualified
if(c[i] >= k + 1){
//reset start pointer
if(findStart == false){
start = i;
findStart = true;
}
//extreme situation such as"aaaaa...."
end = i;
//fix the end situation
if(i == c.length - 1){
if(end - start + 1 >= k){
return Math.max(result, getResult(c, s, start, end, k));
}
}
}
//if c[i] is not qualified
else if(c[i] < k + 1){
//cutting branch, for example "abbbbb...b"
if(i > 0 && s.charAt(i) == s.charAt(i - 1)){
continue;
}
//set end pointer
if(i > 0 && c[i - 1] >= k + 1){
//make sure the previous number is qualified
end = i - 1;
}
if(i != 0 && end - start + 1 >= k){
result = Math.max(result, getResult(c, s, start, end, k));
}
//result findStart pointer each time after calculation
findStart = false;
}
}
return result;
}
//calculate the tmp result
private int getResult(int[] c,String s,int start, int end, int k){
int result = 0;

//add qualified c[i] to the map
Map<Character, Integer> map = new HashMap<>();
for(int i = start; i <= end; i++){
if(!map.containsKey(s.charAt(i))){
map.put(s.charAt(i), 1);
}
else{
map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
}
}

for(int j = end; j >= start; j--){
if(!map.containsKey(s.charAt(j))){
continue;
}
//if c[i] is not qualified
if(map.get(s.charAt(j)) < k){
map.remove(s.charAt(j));
if(map.isEmpty()){
return 0;
}
//fix the last k, avoid out of bound
if(j == s.length() - 1){
return getResult(c, s, start, end - 1, k);
}
//cut the selected array from the end, "bbbbbbbcded"
if(map.get(s.charAt(j + 1)) == null){
return getResult(c, s, start, end - 1, k);
}
//cut the selected array from the beginning, "abbbbbbb"
else{
return getResult(c, s, start + 1, end, k);
}
}
//if c[i] is qualified
else{//map.get(c[j] >= k)
//fix the bound
if(j == start){
return end - start + 1;
}
}
}
return result;
}``````

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