LeetCode 340. Longest Substring with At Most K Distinct Characters

LC address: 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.

For example, Given s = “eceba” and k = 2,

T is “ece” which its length is 3.

Analysis:

需要使用start pointer和end pointer来标记我们考察的substring，利用Hashtable记录这个substring中每一个char的最后index。移动end pointer的时候更新value或者增加新entry，移动start pointer的时候视情况删除entry（如果table(s.charAt(start)) == start的话）。

Solution:

import java.util.*;

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k <= 0) {
            return 0;
        }
        int length = 0;
        int start = 0;
        int end = 0;
        Hashtable lastTable = new Hashtable();
        while (end < s.length()) {
            if (lastTable.size() <= k) {
                lastTable.put(s.charAt(end), end);
                length = Math.max(end - start, length);
                end += 1;
                if (end == s.length() && lastTable.size() <= k) {
                    length = Math.max(end - start, length);
                }
            } else {
                while (start != lastTable.get(s.charAt(start))) {
                    start += 1;
                }
                lastTable.remove(s.charAt(start));
                start += 1;
            }
        }
        return length;
    }
}

Solution code can also be found here: https://github.com/all4win/LeetCode.git