Problem

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".

JavaScript Code

function maxSubStringKUniqueChars(s, k) {
    //declare a counter
    var map = {};       
    var start = 0;
    var maxLen = 0;
    var maxSubstring = null;
 
    for (var i = 0; i < s.length; i++) {
        //add each char to the counter
        var c = s.charAt(i);
        if(map[c]!=null){
            map[c] = map[c]+1;
        }else{
            map[c] = 1;
        }
 
        if(Object.keys(map).length == k+1){
            //get maximum
            var range = i-start;
            if(range > maxLen){
                maxLen = range;
                maxSubstring = s.substring(start, i);
            }
 
            //move left cursor toward right, so that substring contains only k chars
            var first = s.charAt(start);
            while(Object.keys(map).length > k){
                var count = map[first];
                if(count>1){
                    map[first] = count-1;
                }else{
                    delete map[first];
                }
                start++;
            }
        }
    }
 
    if (Object.keys(map).length == k && maxLen == 0) {
        return s;
    }
 
    return maxSubstring;
}
console.log(maxSubStringKUniqueChars('abcabcbb', 3));

0 comments:

Blogroll

Follow this blog by Email

Popular Posts