Simple, Easy to understand Divide and Conquer solution


  • 0
    C
    public class Solution {
        public int longestSubstring(String s, int k) {
            if (s.length() == 0 || k > s.length()) return 0;
            return longestSubString(0, s.length(), s, k);
        }
        
        public int longestSubString(int start, int end, String s, int k) {
            if (end - start < k) return 0;
            int max = 0;
            int[] map = new int[26];
            for (int i = start; i < end; i++) {
                map[s.charAt(i) - 'a']++;
            }
            for (int i = start; i < end; i++) {
                int count = map[s.charAt(i) - 'a'];
                if (count > 0 && count < k) {
                    return Math.max(longestSubString(start, i, s, k), longestSubString(i + 1, end, s, k));
                }
            }
            return end-start;
        }
    }
    

Log in to reply
 

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