O(n) time Complexity solution


  • 1
    F
    // convert to get actual n unique no less than k 
        // just 26 will be ok
        public int longestSubstring(String s, int k) {
            int res = 0;
            for (int i = 1; i <= 26; i++) {
                int r = subProblem(s, k, i);
                res = Math.max(res, r);
            }
            return res;
        }
        
        private int subProblem(String s, int k, int h) {
            int left = 0, count = 0, kCounter = 0, res = 0;
            int[] counter = new int[26];
            for (int i = 0; i < s.length(); i++) {
                counter[s.charAt(i)-'a']++;
                if (counter[s.charAt(i)-'a'] == k) kCounter++;
                if (counter[s.charAt(i)-'a'] == 1) {
                    count++;
                    while (left <= i && count > h) {
                        counter[s.charAt(left)-'a']--;
                        if (counter[s.charAt(left)-'a'] == 0) count--;
                        if (counter[s.charAt(left)-'a'] == k-1) kCounter--;
                        left++;
                    }
                }
                if (count == h && kCounter == h) {
                    res = Math.max(res, i-left+1);
                }
            }
            return res;
        }

Log in to reply
 

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