Java O(n) Solution


  • 0
    A
    class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if (k == 0) return 0;
            int i = 0, j = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            int max_length = 0;
            while (j < s.length()) {
                while (j < s.length()) {
                    char c = s.charAt(j);
                    if (map.containsKey(c)) {
                        map.put(c, map.get(c) + 1);
                        j++;
                    } else if (map.size() < k) {
                        map.put(c, 1);
                        j++;
                    } else {
                        break;
                    }
                }
                if (j - i > max_length) max_length = j - i;
                while (map.size() == k) {
                    char c = s.charAt(i);
                    int occurences = map.get(c);
                    i++;
                    if (occurences == 1) {
                        map.remove(c);
                        break;
                    } else {
                        map.put(c, occurences - 1);
                    }
                }
            }
            return max_length;
        }
    }
    

Log in to reply
 

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