Easy understanding Java Solution beats 97%


  • 0
    S

    The idea is to keep a counts array that will capture the occurrences of a character in the string. Later start iterating the string and whenever you encounter a character that is not more than 'K' times in the string, you stop and check if the string until now is valid (i.e. all the characters until now occur k times). If not you call the function again with the substring. This function call will give us the maximum length of the string. Consider an example:

    "abababacabadccccc" and k as "3"

    Now since the counts look like this:
    a -> 6
    b -> 4
    c- > 6
    d -> 1

    The function until it encounters the char 'd' will accumulate the count. Now when it sees a 'd' it needs to check if the current string is valid. It is not valid because, 'c' occurs only once (< k) times. As such we now call the function again with this substring "abababacaba". Now here the counts are calculated again, and it'll look like this:

    a -> 6
    b -> 4
    c -> 1 (< k)

    Now it'll accumulate the count. Now when it encounters 'c' a validation is done and we see that the string is valid because both 'a' and 'b' occur more than 'k' times. So it'll send the count as 7. Had it not been valid another function call would be made to get the count for the substring and so on.

    Hope the explanation is clear.

    class Solution {
        public int longestSubstring(String s, int k) {
            int length = s.length();
    	char[] chars = s.toCharArray();
    	int[] counts = new int[26];
    	int[] curCount = new int[26];
    
    	for(int i = 0; i < length; ++i) {
    	    counts[chars[i] - 'a']++;
    	}
    
    	int max = 0;
    	int count = 0;
    	int curStart = 0;
    
    	for(int i = 0; i < length; ++i) {
                if(counts[chars[i] - 'a'] >= k) {
    	        curCount[chars[i] - 'a']++;
    		count++;
    	    } else {
    	        if(count > 0 && validSubstring(curCount, k)) {
    		    max = Math.max(max, count);
    		} else if(count > max){
    		    max = Math.max(max, longestSubstring(s.substring(curStart, i), k));
    		}
    		count = 0;
    		curStart = i + 1;
    		curCount = new int[26];
    	    }
        }
    
    	if(count > 0 && validSubstring(curCount, k)) {
    	    max = Math.max(max, count);
    	} else if (count > max){
    	    max = Math.max(max, longestSubstring(s.substring(curStart), k));
    	}
    
    	return max;
        }
    
        public boolean validSubstring(int[] curCount, int k) {
    	for(int j = 0; j < 26; ++j) {
        	    if(curCount[j] != 0 && curCount[j] < k) {
    	        return false;
    	    }
            }
    	return true;
        }
    }
    

    The runtime in the worst case is O(n2).
    if you however fail to put "count > max" condition in the below condition, then it'll be a stackoverflow exception.

    } else if (count > max){
          max = Math.max(max, longestSubstring(s.substring(curStart), k));
    }
    

Log in to reply
 

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