Java solution using recursion


  • 0
    H

    the runtime for this solution is 24ms, perhaps the .replace() method is too expensive, but it is the most concise way I can think of.

    import java.util.TreeMap;
    
    public class Solution {
    	public int longestSubstring(String s, int k) {
    		if (s == null || s.length() < k) {
    			return 0;
    		} else if (k <= 1) {
    			return s.length();
    		}
    
    		//use a treemap to sort the occurrence of every character in the string
    		TreeMap<Integer, String> map = new TreeMap<Integer, String>();
    		String temp = s;
    		while (temp.length() > 0) {
    			int count = temp.length();
    			String c = temp.substring(0,1);
    			temp = temp.replace(c, "");
    			map.put(count - temp.length(), c);
    		}
            
    
    		if (map.firstKey() >= k) {
    			//if the number of occurrence of the least repeating character in 's' is 
    			//already greater than 'k', then the string is good to go
    			return s.length();
    		} else {
    			//since the least repeating character WILL ABSOLUTELY NOT show up in the longest substring
    			//split the string by that and start recursion, keep count updated to the largest number.
    			int count = 0;
    			for (String sub : s.split(map.get(map.firstKey()))) {
    				count = Math.max(longestSubstring(sub, k), count); //recursion here
    			}
    			return count;
    		}
    	}
    }
    

Log in to reply
 

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