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

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

## 题目地址

[https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/](https://leetcode.com/problems/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_)

```java
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

```java
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;
    LinkedHashMap<Character, Integer> hashmap = new LinkedHashMap<Character, Integer> (k + 1);
    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;
  }
}
```
