Java 5ms substring


  • 1
    K

    After counting every character, go through the string and do recursive calls on substrings between the characters with count < k.

    public class Solution {
        public int longestSubstring(String s, int k) {
            return helper(s, k, 0, s.length() - 1);
        }
        private int helper(String str, int k, int start, int end) {
            if (end - start + 1 < k) return 0;
            int[] count = new int[26];
            for (int i = start; i <= end; i++) {
                count[str.charAt(i) - 'a']++;
            }
            
            int max = Integer.MIN_VALUE;
            int prev = start;
            for (int i = start; i <= end; i++) {
                int c = count[str.charAt(i) - 'a'];
                if (c > 0 && c < k) {
                    max = Math.max(max, helper(str, k, prev, i - 1));
                    prev = i + 1;
                }
            }
            if (prev != start) 
                return Math.max(max, helper(str, k, prev, end));
            return end - start + 1;
        }
    }
    

Log in to reply
 

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