Java Divide & Conquer BitMap & Two-Pointer Solution


  • 0
    A
        public int longestSubstring(String s, int k) {
            return helper(s.toCharArray(), 0, s.length(), k);
        }
        
        private int helper (char ch[], int start, int end, int k) {
            if (end - start < k) return 0;
            int tmp[] = new int[26];
            int bits = 0;
            for (int i = start; i < ch.length && i < end; i++) {
                tmp[ch[i] - 'a']++;
                if (tmp[ch[i] - 'a'] >= k) bits &= (0xffffffff ^ (1 << (ch[i] - 'a')));
                else bits |= (1 << (ch[i] - 'a'));
            }
            if (bits == 0) return end - start;
            int i = ch.length - 1;
            int j = ch.length;
            int max  = 0;
            while (i >= start && j > i) {
                if ((bits & (1 << (ch[i] - 'a'))) != 0) {
                    max = Math.max(helper(ch, i + 1, j, k), max);
                    j = i;
                }
                i--;
            }
            return Math.max(helper(ch, i + 1, j, k), max);
        }
    }

Log in to reply
 

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