# Java HashMap Solution, worst case O((n^2)*26)

• These commented blocks are for speeding up the code, in case of Time Limit Exceed.Basically,denote index as the position of each character in String s,I use a HashMap<index,int[]> to store the occurence of all characters in input s[0,index],index inclusively,which, ranges from 0 to s.length()-1;every substring then can be expressed as map.get(i)-map.get(j), 0<=j<i, we can just check whether if it's valid,update the maxLen and also the hashmap.

I was totally inspired by a guy and he gave an idea of solving subarray/substring problem, and it's stunning!
https://discuss.leetcode.com/topic/33537/java-o-n-explain-how-i-come-up-with-this-idea

``````public class Solution {
public int longestSubstring(String s, int k) {
HashMap<Integer,int[]> map=new HashMap<>();
int maxLen=0;
map.put(-1,new int[26]);
for(int i=0;i<s.length();i++){
int[] curr=Arrays.copyOf(map.get(i-1),26);
curr[s.charAt(i)-'a']++;
// if(i+1<k){
//     map.put(i,curr);
//     continue;
// }
for(int j=-1;j<i;j++){
// if(i-j<k){
//     continue;
// }
int[] tmp=map.get(j);
boolean flag=true;
for(int m=0;m<26;m++){
if(curr[m]!=tmp[m]&&curr[m]-tmp[m]<k){
flag=false;
break;
}
}

if(flag){
maxLen=Math.max(maxLen,i-j);
break;
}
}
map.put(i,curr);
}
return maxLen;
}
}
``````

• @bxiao0801 so smart solution, best ever! THX!

• This solution gets TLE for now.

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