Java 3ms recursive solution.


  • 0
    S

    Given a string s, find out all chars that are invalid (i.e., count < k). The longest substring must reside in one of the substrings divided by those invalid chars. We find out all those possible substrings and recursively address each of them.

    NOTE: repeatedly using s.charAt() is actually very slow. If we use charAt() in the following code, the runtime becomes 6ms, doubled!

    Here is the code:

    public class Solution {
        public int longestSubstring(String s, int k) {
            return longestSubstringRecur(s,k);
        }
        
        public int longestSubstringRecur(String s, int k){
            if (s.length()<k) return 0;
            
            char[] charArr = s.toCharArray();
            int[] charCounts = new int[26];
            for (char c : charArr){
                charCounts[c-'a']++;
            }
            
            // Early termination: 
            //  1. invalid: no char in s appears >= k times.
            //  Or 2. Good enough: every char appears >= k times.
            boolean valid = false, goodEnough = true;
            for (int count : charCounts){
                if (count>=k){
                    valid = true;                
                } 
                if (count>0 && count <k){
                    goodEnough = false;
                }
            	if (valid && !goodEnough) break;
            }
            if (!valid) return 0;
            if (goodEnough) return s.length();
            
            // Address every possible substring, i.e., substring between two invalid chars. 
            int p1=0, p2=-1, maxLen=0;
            while (p1<s.length()){
                p2++;
                while (p2<s.length() && charCounts[charArr[p2]-'a']>=k) p2++;
                int curMaxLen = longestSubstringRecur(s.substring(p1,p2),k);
                maxLen = Math.max(maxLen,curMaxLen);
                p1 = p2+1;
            }
            return maxLen;
            
        }
    }

Log in to reply
 

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