Java solution 14 ms Recursive based on splitting string by least frequent character


  • 1
    C
    public class Solution {
        public int longestSubstring(String s, int k) {
            if(s==null || s.length()==0 || k==0 || (s.length()<k)) return 0;
            if(s.length()==1 && k==1) return 1;
           HashMap<Character,Integer> map=new HashMap<Character,Integer>();
            for(char c:s.toCharArray()){
                if(!map.containsKey(c)){
                    map.put(c,1);
                }else{
                    map.put(c,map.get(c)+1);
                }
            }
            int min=Integer.MAX_VALUE;
            char c='a';
            for(char m:map.keySet()){
                if(min> map.get(m)){
                    min=map.get(m);
                    c=m;
                }
            }
            
            if(min>=k) return s.length();
            else{
                String parts[]=s.split(""+c);
                int len=0;
                for(int i=0;i<parts.length;i++){
                    len=Math.max(len,longestSubstring(parts[i],k));
                }
                return len;
            }
        }
    }

  • 0
    C

    Very nice solution, easy to read and intuitive approach. I am struggling to comeup with a intuitive iterative approach.

    Thanks for sharing your solution


Log in to reply
 

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