Generic solution in Java that can be used for Unicode


  • 7
    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.


Log in to reply
 

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