G2 - Longest Substring with At Most K Distinct Characters

May 21, 2017

Given a string, find the longest substring that contains only two unique characters. For example, given "abcbbbbcccbdddadacb", the longest substring that contains 2 unique character is "bcbbbbcccb".

Solution :
Use sliding window and a char map to keep count of unique char
As soon asn unique char becomes more then 1 start increasing left pointer and reduce the count
update the max len of the string found so far

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