Solve this with Recursion


  • 0
    G
        int recFun(char[] str, int s, int e, int k) {
            if (e+1-s < k) {
                return 0;
            }
            Set<Character> set = new HashSet<Character>();
            int[] freq = new int[256]; //could use size of 26 instead
            for (int i = s; i <= e; i ++) {
                char ch = str[i];
                freq[ch] ++;
                if (freq[ch] < k) {
                    set.add(ch);
                }
                else {
                    set.remove(ch);
                }
            }
            
            if (set.isEmpty()) {
                return e - s + 1;
            }
            
            int res = 0;
            int l = s, r = s;
            for (; r <= e; r ++) {
                if (set.contains(str[r])) {
                    res = Math.max(res, recFun(str, l, r - 1, k));
                    l = r + 1;
                }
            }
            if (r > l) {
                res = Math.max(res, recFun(str, l, r - 1, k));
            }
            
            return res;
        }
        
        public int longestSubstring(String s, int k) {
            int len = s.length();
            char[] str = s.toCharArray();
            return recFun(str, 0, len - 1, k);
        }

Log in to reply
 

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