Coding Challenge #12

Daily Coding Problem #13

 // Daily Coding Problem #13
// With integer dLimit and string str, return the longest substring of str that contains at most dLimit distinct characters
// (so the goal is to look for letter duplication sections, they score higher)
// example: dLimit=2, 'aasdf': 'aas' has 2 distinct chars 'a' and 's', while being longest
// example 2: dLimit=2, 'hoooow?' : 'hoooo' or 'oooow', either.
// example 3: dLimit=3, 'hoooow?' : 'hoooow' or 'oooow?', either
function checkStr(str, dLimit){
    var ostr = "";
    for(var xint = 0, len = str.length;xint < len;xint++){ // check each char as a new sequence
        var distinctLeft = dLimit;
        var streakChars = [];
        var tmpStr = "";
        for(var yint = xint;yint < len;yint++){ // go through the sequence and find longest substring with dLimit distinct chars
            var inStreak = false;
            for(var zint = 0, zlen = streakChars.length;zint < zlen;zint++){ // check streakChars to see whether this one is distinct
                var candidate = str.charAt(yint);
                if(streakChars[zint] == candidate){
                    inStreak = true;
                    break;
                }
            }
            
            if(inStreak){ // already in streakChars
                tmpStr += str.charAt(yint);
            }else{ // new char in streak
                distinctLeft--;
                if(distinctLeft < 0) // this char would be too many for dLimit
                    break;
                streakChars.push(str.charAt(yint));
                tmpStr += str.charAt(yint);
            }
        }
        if(tmpStr.length > ostr.length) ostr = tmpStr; // update longest substring found within dLimit distinct chars
    }
    return ostr;
}

function test(str, dLimit){
    console.log('dLimit = ' + dLimit + ', string = \'' + str + '\'. Result: \'' + checkStr(str, dLimit) + '\'');
}
function testRan(){ // generate random strings to test
    var dLimit = Math.floor(Math.random() * 2) + 2; // dLimit will be [2,4] inclusive
    var strLen = Math.floor(Math.random() * 5) + 5; // string length will be [5,10] inclusive
    var aCode = 'a'.charCodeAt(0);
    var testStr = "";
    for(var xint = 0;xint < strLen;xint++) // generate random letters [a,f]
        testStr += String.fromCharCode(aCode + Math.floor(Math.random()*5));
    
    test(testStr, dLimit);
}

test('hahaf', 2);
test('hahaf', 3);
test('doodle', 2);
test('doodle', 3);
test('manhandle', 3);
test('bazooka', 3);
for(var rint = 0;rint < 5;rint++) testRan();