[Java]10 lines. Constant space use.

  • 0
    public int longestSubstring(String s, int k) {
        if(k==0||s.length()==0) return 0;
        int dict[]=new int[26],max=0;
        String regular="";
        for(int i=0;i<s.length();i++) dict[s.charAt(i)-'a']++;
        for(int i=0;i<26;i++) if(dict[i]>0&&dict[i]<k) regular=regular+(char)(i+'a'); //pick out all the invalid ones
        if(regular.length()==0) return s.length();
        String []subs=s.split("["+regular+"]");  //use the system function call to eliminate all invalid ones
        for(int i=0;i<subs.length;i++) max=Math.max(longestSubstring(subs[i],k),max);
        return max;

  • 1

    How can String []subs=s.split("["+regular+"]"); be "Constant space use"?

Log in to reply

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