Comment on page

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

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;
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;
}
}