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

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