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