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


  • 7

    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;
        }
    }
    

  • 0
    I

    @bxiao0801 so smart solution, best ever! THX!


  • 1
    N

    This solution gets TLE for now.


Log in to reply
 

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