LeetCode 340 - Longest Substring with At Most K Distinct Characters

(Leetcode) Longest Substring with At Most Two Distinct Characters | Changhaz's Codeplay

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.

X. https://discuss.leetcode.com/topic/41671/15-lines-java-solution-using-slide-window

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] count = new int[256];
        int num = 0, i = 0, res = 0;
        for (int j = 0; j < s.length(); j++) {
            if (count[s.charAt(j)]++ == 0) num++;
            if (num > k) {
                while (--count[s.charAt(i++)] > 0);
                num--;
            }
            res = Math.max(res, j - i + 1);
        }
        return res;
    }

A more generic solution as follows, can be solution for Unicode string:

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0;
    int best = 0;
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        map.put(c, map.getOrDefault(c, 0) + 1);
        while (map.size() > k) {
            char leftChar = s.charAt(left);
            if (map.containsKey(leftChar)) {
                map.put(leftChar, map.get(leftChar) - 1);                     
                if (map.get(leftChar) == 0) { 
                    map.remove(leftChar);
                }
            }
            left++;
        }
        best = Math.max(best, i - left + 1);
    }
    return best;
} 

http://www.danielbit.com/blog/puzzle/leetcode/leetcode-longest-substring-with-at-most-two-distinct-characters

最优的解法应该是维护一个sliding window，指针变量i指向sliding window的起始位置，j指向另个一个字符在sliding window的最后一个，用于定位i的下一个跳转位置。内部逻辑就是
1）如果当前字符跟前一个字符是一样的，直接继续。
2）如果不一样，则需要判断当前字符跟j是不是一样的
a）一样的话sliding window左边不变，右边继续增加，但是j的位置需要调整到k-1。
b）不一样的话，sliding window的左侧变为j的下一个字符（也就是去掉包含j指向的字符的区间），j的位置也需要调整到k-1。

在对i进行调整的时候（1.a），需要更新maxLen。

[注意事项]
1）在最后返回的时候，注意考虑s.length()-i这种情况，也就是字符串读取到最后而没有触发（1.a）
2）讲解清楚sliding window的更新
3）该题目有个follow-up，就是如果是k个distinct characters怎么办。这样的话就只能对所有可能的字符用一个数组去做counting，而且只能假设ASIC字符集256。Unicode太大了。

public int lengthOfLongestSubstringTwoDistinct(String s) {
        int i = 0, j = -1, maxLen = 0;
        for (int k = 1; k < s.length(); k++) {
            if (s.charAt(k) == s.charAt(k - 1)) continue;
            if (j >= 0 && s.charAt(j) != s.charAt(k)) {
                maxLen = Math.max(k - i, maxLen);
                i = j + 1; 
            }
            j = k - 1;  
        }
        return Math.max(s.length() - i, maxLen);
    }

另一种方法是，维护一个sliding window保证这个窗口中的字符串最多只有两种，维护start和end的指针，记录每个字符出现的次数，当第三个字符出现时，加入到map中，并且把map中记录的start位置上的字符串删掉，如果start位置上的字符串有多个，就循环将计数器减一，直到为零，然后删除start位置的字符串
Based on http://sidefaraway.blogspot.com/2014/12/leetcode-longest-substring-with-at-most.html
public static int findMaxKCharSubstring(String s, int k) {
Map<Character, Integer> charNum = new HashMap<Character, Integer>();
int start = 0;
int end = 0;
// int charType = 2; //can be k
int maxLen = 0;
while (end < s.length()) {
char cur = s.charAt(end);
// if this char is in substring already, then increase its number
if (charNum.containsKey(cur)) {
charNum.put(cur, charNum.get(cur) + 1);
} else {
charNum.put(cur, 1);
if (charNum.size() > k) {
// We need eliminate another char in substring to maintain
// the feasibility of the substring.
while (charNum.get(s.charAt(start)) > 0
&& charNum.size() > k) {
int newCount = charNum.get(s.charAt(start)) - 1;
if (newCount > 0) {
charNum.put(s.charAt(start), newCount);
} else {
charNum.remove(s.charAt(start));
}
start++;
}
}
}
if (maxLen < end - start + 1) {
maxLen = end - start + 1;
}
end++;
}
return maxLen;
}

Leetcode Longest Substring with At Most Two Distinct Characters

1.     int lengthOfLongestSubstringTwoDistinct(string s) {  
2.         int len = s.length();  
3.         unordered_map<char,int> existingChars;  
4.         int cnt = 0, longest = 0, st = 0;  
5.         for(int ed = 0; ed < len; ed++){  
6.             if(existingChars[s[ed]]==0){  
7.                cnt++;  
8.             }  
9.             existingChars[s[ed]]++;  
10.             for(;cnt>2;st++){  
11.                 existingChars[s[st]]--;  
12.                 if(existingChars[s[st]]==0){  
13.                     cnt--;  
14.                 }  
15.             }  
16.             longest = max(longest, ed-st+1);  
17.         }  
18.         return longest;  
19.     } 

Related:
LeetCode] Longest Substring Without Repeating Characters 解题报告
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

1:       int lengthOfLongestSubstring(string s) {  
2:            int count[26];  
3:            memset(count, -1, 26*sizeof(int));  
4:            int len=0, maxL = 0;  
5:            for(int i =0; i< s.size(); i++,len++)  
6:            {  
7:                 if(count[s[i]-'a']>=0)  
8:                 {  
9:                      maxL = max(len, maxL);  
10:                      len =0;          
11:                      i = count[s[i]-'a']+1;  
12:                      memset(count, -1, 26*sizeof(int));   
13:                 }  
14:                 count[s[i]-'a']=i;  
15:            }      
16:            return max(len, maxL);  
17:       }

https://changhaz.wordpress.com/2014/11/26/leetcode-longest-substring-with-at-most-two-distinct-characters/

Solution 1:
Keep a sliding window of valid substring with at most 2 distinct characters. Keep track of the index of the last appearance of each of the 2 characters within the window. Use -1 as the default value of the index.

ai: the smaller index of the two last appearance indices
bi: the lager index of the two last appearance indices

We always have ai smaller than bi.

For example, in the example eceba, for window ece, the last appearance index for character c is 1, the last appearance for character e is 2. So here ai equals 1 and bi equals 2;

https://wwwx.cs.unc.edu/~duozhao/entry/2014/12/543/
http://blog.csdn.net/whuwangyi/article/details/42451289

 public int lengthOfLongestSubstringTwoDistinct(String s) {
  int start = 0;
  int maxLen = 0;

  // Key: letter; value: the index of the last occurrence.
  Map<Character, Integer> map = new HashMap<Character, Integer>();
  int i;
  for (i = 0; i < s.length(); ++i) {
   char c = s.charAt(i);
   if (map.size() == 2 && !map.containsKey(c)) {
    // Pick the character with the leftmost last occurrence.
    char charEndsMostLeft = ' ';
    int minLast = s.length();
    for (char ch : map.keySet()) {
     int last = map.get(ch);
     if (last < minLast) {
      minLast = last;
      charEndsMostLeft = ch;
     }
    }

    map.remove(charEndsMostLeft);
    start = minLast + 1;
   }
   map.put(c, i);
   maxLen = Math.max(maxLen, i - start + 1);
  }
  return maxLen;
 }

Longest Substring with At Most K Distinct Characters

 public int lengthOfLongestSubstringKDistinct(String s, int k) {
  int start = 0;
  int maxLen = 0;

  // Key: letter; value: the number of occurrences.
  Map<Character, Integer> map = new HashMap<Character, Integer>();
  int i;
  for (i = 0; i < s.length(); ++i) {
   char c = s.charAt(i);
   if (map.containsKey(c)) {
    map.put(c, map.get(c) + 1);
   } else {
    map.put(c, 1);
    while (map.size() > k) {
     char startChar = s.charAt(start++);
     int count = map.get(startChar);
     if (count > 1) {
      map.put(startChar, count - 1);
     } else {
      map.remove(startChar);
     }
    }
   }

   maxLen = Math.max(maxLen, i - start + 1);
  }

  return maxLen;
 }

http://www.programcreek.com/2013/02/longest-substring-which-contains-2-unique-characters/
Time is O(n).
https://discuss.leetcode.com/topic/119/longest-subsequence-of-distinct-characters/2

Return length of the Longest subsequence of distinct characters from a stream of character.
The stream can be very long and saving the whole stream in memory is not an option.//following method is used to receive new char from the stream put(char c)

but the stream makes it a little complicated

I think with a hash-table and a pointer which records the current start point will apply to this problem.

using sliding (rolling) window and hash for each character.

X. follow up
https://discuss.leetcode.com/topic/48827/java-o-nlogk-using-treemap-to-keep-last-occurrence-interview-follow-up-question
 The interviewer may say that the string is given as a steam. In this situation, we can't maintain a "left pointer" as the classical O(n) hashmap solution.

some interviewer may require this solution as a followup. Instead of recording each char's count, we keep track of char's last occurrence. If you consider k as constant, it is also a O(n) algorithm.

inWindow keeps track of each char in window and its last occurrence position

lastOccurrence is used to find the char in window with left most last occurrence. A better idea is to use a PriorityQueue, as it takes O(1) to getMin, However Java's PQ does not support O(logn) update a internal node, it takes O(n). TreeMap takes O(logn) to do both getMin and update.
Every time when the window is full of k distinct chars, we lookup TreeMap to find the one with leftmost last occurrence and set left bound j to be 1 + first to exclude the char to allow new char coming into window.

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

Read full article from (Leetcode) Longest Substring with At Most Two Distinct Characters | Changhaz's Codeplay