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/

题目描述

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