Number Of Annagram Pair Substrings In A String

numberOfAnnagramPairs.js

var maxNStored = 1;
var storedFactorials = [1n, 1n]
function getFactorial(n){
    //We can say that if n is not in our stored factors, no other factorials
    //are in there. Don't worry, we can't fill that stored factorial list
    //up too big as factorials get big FAST.
    if(n > maxNStored){
        let factorial = storedFactorials[maxNStored];
        for(let i = maxNStored + 1; i <= n; ++i){
            factorial *= BigInt(i);
            storedFactorials.push(factorial);
        }
        maxNStored = n;
    }
    return storedFactorials[n];
}

function hash(s){
    //I initially wanted to do a bitmask hash
    //xor'd, but the amount of each letter is important
    //therefore, the far better solution is to just sort
    //the letters as we go.
    s.sort();
    return s.join('');
}

function recursiveAnnagramSearch(s, numIterations){
    if(numIterations == s.length){
        return 0;
    }

    let annagramHash = {};
    let annagramKeys = [];
    const subStringLength = s.length - numIterations;
    for(let i = 0; i <= numIterations; ++i){
        const subArray = s.slice(i, i + subStringLength);
        const stringHash = hash(subArray);
        console.log(stringHash);
        if(annagramHash.hasOwnProperty(stringHash)){
            annagramHash[stringHash] += 1;
        }
        else{
            annagramHash[stringHash] = 1;
            annagramKeys.push(stringHash);
        }
    }

    //Now count the number of annagrams at this level by counting the number of
    //combinations of our number of substrings with these ids
    let pairs = 0;
    for(let i = 0, numAnnagramKeys = annagramKeys.length; i < numAnnagramKeys; ++i){
        //The number of pairs is the number of combinations of annagram keys
        let num = annagramHash[annagramKeys[i]];
        if(num > 1){
            pairs += Number(getFactorial(num) / (2n * getFactorial(num - 2)));
        }
    }

    return pairs + recursiveAnnagramSearch(s, numIterations + 1);
}

// Complete the sherlockAndAnagrams function below.
function sherlockAndAnagrams(s, numIterations = 1) {
    //S is a 100, so it isn't terribly huge.
    //we do need to break the string apart into all substrings
    //and a recursive method would probably do fine.
    //
    //The number of anagrams at each level of recursion can be added to
    //the previous version.
    //
    //Rather then checking each character to see what annagrams
    //can be made, we instead run them through getStringId
    //to hash each string, and add new values as we go.
    //When we have finished iterating through all elements of s
    //we return the number of annagrams.
    const sArray = s.split('');
    return recursiveAnnagramSearch(sArray, 1);
}