Extensible solution to k = 2


  • 0
    J

    The difference between the question without repeating characters and with at most k distinct characters is that when we remove i, we need to decide the frequency we encountered. So for the former one, we only need hashset, but for latter one we need hashmap to record the frequency.

    public class Solution {
        public int lengthOfLongestSubstringKDistinct(String s, int k) {
            if (s == null || s.length() == 0 || k == 0) {
                return 0;
            }
            int i = 0;
            int j = 0;
            int len = 0;
            Map<Character, Integer> map = new HashMap<Character, Integer>();
            for (i = 0; i < s.length(); i++) {
                while (j < s.length()) {
                    char c = s.charAt(j);
                    if(map.size() < k) {
                        if (!map.containsKey(c)) {
                            map.put(c, 1);
                        } else {
                            map.put(c, map.get(c) + 1);
                        }
                        j ++;
                    } else if (map.size() == k && map.containsKey(c)) {
                        map.put(c, map.get(c) + 1);
                        j ++;
                    } else {
                        break;
                    }
                }
                len = Math.max(len, j - i);
                if (map.get(s.charAt(i)) == 1) {
                    map.remove(s.charAt(i));
                } else {
                    map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
                }
            }
            return len;
        }
    }
    

    And my code for without repeating characters

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            int i = 0;
            int j = 0;
            int ans = 0;
            Set<Character> set = new HashSet<Character>();
            for (i = 0; i < s.length(); i++) {
                while (j < s.length()) {
                    if (!set.contains(s.charAt(j))) {
                        set.add(s.charAt(j));
                        j ++;
                    } else {
                        break;
                    }
                }
                ans = Math.max(ans, j - i);
                set.remove(s.charAt(i));
            }
            return ans;
        }
    }
    

Log in to reply
 

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