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.

Time: O(N) && Space: OK1)
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int n = s.length();
if (n*k == 0) return 0;
​
// sliding window left and right pointers
int left = 0;
int right = 0;
// hashmap character -> its rightmost position
// in the sliding window
HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
​
int max_len = 1;
while (right < n) {
// add new character and move right pointer
hashmap.put(s.charAt(right), right++);
​
// slidewindow contains 3 characters
if (hashmap.size() == k + 1) {
// delete the leftmost character
int del_idx = Collections.min(hashmap.values());
hashmap.remove(s.charAt(del_idx));
// move left pointer of the slidewindow
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;
​
// sliding window left and right pointers
int left = 0;
int right = 0;
LinkedHashMap<Character, Integer> hashmap = new LinkedHashMap<Character, Integer>(k+1);
​
int max_len = 1;
​
while (right < n) {
Character character = s.charAt(right);
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;
}
}

Approach #3 TreeMap

public class Solution {
public int lengthOfLongestSubstringKDistinct(String str, int k) {
if (str == null || str.isEmpty() || k == 0) {
return 0;
}
TreeMap<Integer, Character> lastOccurrence = new TreeMap<>();
Map<Character, Integer> inWindow = new HashMap<>();
int j = 0;
int max = 1;
for (int i = 0; i < str.length(); i++) {
char in = str.charAt(i);
while (inWindow.size() == k && !inWindow.containsKey(in)) {
int first = lastOccurrence.firstKey();
char out = lastOccurrence.get(first);
inWindow.remove(out);
lastOccurrence.remove(first);
j = first + 1;
}
//update or add in's position in both maps
if (inWindow.containsKey(in)) {
lastOccurrence.remove(inWindow.get(in));
}
inWindow.put(in, i);
lastOccurrence.put(i, in);
max = Math.max(max, i - j + 1);
}
return max;
}
}