刷题（5）leetcode 340. -- sliding w

 昨天晚上真的是太困了，哄娃睡觉就直接睡着了。孩子睡的也比较晚，睡着大概也要晚上十一点了。昨天开始又是轮到值班，白天上班也是很忙。还是很感激队友能够帮忙不少的。比如早上我要开会，队友就帮孩子起床穿衣洗漱吃早饭。感恩。没有人帮忙的时候，真的感觉夫妻互相扶持很重要。

刚刷了一道340. Longest Substring with At Most K Distinct Characters。这是一道medium。题目给出一个string s， 一个整数k，要求找出s中至多包含k个distinct character的最长substring。

e.g: input: s = "eceba", k = 2; output:3

solution: two pointers (sliding window)

my solution:

class Solution {

    public int lengthOfLongestSubstringKDistinct(String s, int k) {

        int n = s.length();

        if (n * k == 0) {

            return 0;

        }

        int i = 0, j =0;

        Map<Character, Integer> map = new HashMap<Character, Integer>();

        Set<Character> distinct = new HashSet<>();

        int max_length = 0;

        while(j<s.length()) {

            char current = s.charAt(j);

            map.put(current, map.getOrDefault(current, 0) + 1);

            if(map.get(current) == 1) {

                distinct.add(current);

            }

            while(distinct.size() > k) {

                char toBeRemoved = s.charAt(i);

                map.put(toBeRemoved, map.get(toBeRemoved) - 1);

                if(map.get(toBeRemoved) == 0) {

                    distinct.remove(toBeRemoved);

                }

                i++;

            }

            max_length = Math.max(max_length, j-i+1);

            j++;

        }

        return max_length;

    }

}

time complexity: O(n) n is s.length, because the solution iterate the whole string once

space complexity: O(n), there is a map and a set.