Generic solution in Java that can be used for Unicode


  • 8
    Y

    This problem can be solved using two pointers. The important part is while (map.size() > k), we move left pointer to make sure the map size is less or equal to k. This can be easily extended to any number of unique characters.

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int best = 0;
        for(int i = 0; i < s.length(); i++) {
            // character at the right pointer
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
            // make sure map size is valid, no need to check left pointer less than s.length()
            while (map.size() > k) {
                char leftChar = s.charAt(left);
                map.put(leftChar, map.get(leftChar) - 1);                     
                if (map.get(leftChar) == 0) { 
                    map.remove(leftChar);
                }
                left++;
            }
            best = Math.max(best, i - left + 1);
        }
        return best;
    }

  • 1

    Actually, u can use array instead of hash map, which may be a little faster.


  • 0
    V

    @wutong1111 his point seems to be to make it work for unicode, generalizing the array approach.


  • 0

    Thanks for clearly explaining the solution! Is the time complexity O(N) or O(N*k)? I see other solutions imply the time complexity is O(N), but it seems it's O(N*k), since it has a double loop. Could you please explain?


  • 0
    D

    @L0u1s k is a constant.


  • 0

    Really easy to understand solution. Others felt "out there" for a noob like myself.

    I converted this into JavaScript easily:

    var lengthOfLongestSubstringKDistinct = function(s, k) {
        let map = new Map();
        let left = 0, best = 0;
        
        for (let i = 0; i < s.length; i++) {
            let c = s.charAt(i); // right
            map.set(c, map.has(c) ? map.get(c) + 1 : 1);
            while (map.size > k) {
                let leftChar = s.charAt(left);
                map.set(leftChar, map.get(leftChar) - 1);
                if (map.get(leftChar) === 0) {
                    map.delete(leftChar);
                }
                left++;
            }
            best = Math.max(best, i - left + 1);
        }
        
        return best;
    };
    

  • 0

    @deadmouse said in Generic solution in Java that can be used for Unicode:

    @L0u1s k is a constant.

    How's k a constant? It's an input to the problem and k can be at big as n isn't it?


Log in to reply
 

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