Comment on page

# 340.Longest-Substring-with-At-Most-K-Distinct-Characters

## 题目描述

Given a string, find the length of the longest substring T that contains at most k distinct characters.
Example 1:
Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.
Example 2:
Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

## 代码

### Approach 1: Sliding Window + Hashmap

Complexity Analysis
• Time complexity : O(N)
• Space complexity : O(k)
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int n = s.length();
if (n * k == 0) return 0;
int max_len = 1;
HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
int left = 0;
int right = 0;
while (right < n) {
hashmap.put(s.charAt(right), right++);
if (hashmap.size() == k + 1) {
int del_idx = Collections.min(hashmap.values());
hashmap.remove(s.charAt(del_idx));
left = del_idx + 1;
}
max_len = Math.max(max_len, right - left);
}
return max_len;
}
}

### Approach #2 Sliding Window + Ordered Dictionary

class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int n = s.length();
if (n * k == 0) return 0;
int left = 0;
int right = 0;
int max_len = 1;
while (right < n) {
Characer character = s.charAt(right);
// if character is already in the hashmap -
// delete it, so that after insert it becomes
// the rightmost element in the hashmap
if (hashmap.containsKey(character)) {
hashmap.remove(character);
}
hashmap.put(character, right++);
if (hashmap.size() == k + 1) {
Map.Entry<Character, Integer> leftmost = hashmap.entrySet().iterator().next();
hashmap.remove(leftmost.getKey());
left = leftmost.getValue() + 1;
}
max_len = Math.max(max_len, right - left);
}
return max_len;
}
}