Leetcode Daily - August 13, 2020

Iterator for Combinator

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Design an Iterator class, which has:

• A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• A function next() that returns the next combination of length combinationLength in lexicographical order.
• A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• There will be at most 10^4 function calls per test.
• It's guaranteed that all calls of the function next are valid.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS or BFS

(Submission - Accepted)

I decided to use the following data structures for my class:

• Store the characters as a string and combinationLength as a number
• Use the idea of a mask consisting of 0's and 1's. This is to determine which characters from the character string will be used to form the output string of .next()
• Also generate and store all possible masks when the constructor is run. The main reason for this is that I am familiar with using search/backtracking to create all the permutations of ones and zeros, but if I'm not sure how best to iterate from one given permutation to the next.

Once the array of all possible masks is calculated, .next() and .hasNext() become pretty easy if we are storing the mask index.

• .next() iterates the mask index and then uses the mask to return a string.

• .hasNext() just check to see if the mask index is not the last index of the array.

Submitted Code in Javascript:

var CombinationIterator = function(characters, combinationLength) {
    this.characters = characters
    this.combinationLength = combinationLength 
    // should we generate all combinations now? or when the methods are called? 
    // for testing purposes let's generate them now 
    // string mask of characters 

    this.mask = []

    // to keep lexographical order we need bfs 
    let stack = ['']
    const charLength = characters.length 
    while (stack.length > 0) {
        // if length is 6, add it to this.mask 
        // else, add the possible combinations to the stack 
        // prefer adding 1's first up to combinationLength 
        const currCombo = stack.shift()
        if (currCombo.length === charLength) {
            this.mask.push(currCombo)
        } else if (currCombo.length < charLength) {
            // regex match /<char>/g returns array, so length of that 
            if ((currCombo.match(/1/g) || []).length < combinationLength) {
                stack.push(currCombo+"1")
            }
            if ((currCombo.match(/0/g) || []).length < charLength - combinationLength) {
                stack.push(currCombo+"0")
            }
        }
    }

    this.maskInd = -1
    console.log('initial masks: ', this.mask)

};

/**
 * @return {string}
 */
CombinationIterator.prototype.next = function() {
    this.maskInd ++ 
    const currMask = this.mask[this.maskInd]
    let result = ''
    for (let i = 0; i < currMask.length; i++) {
        if (currMask[i] === "1") {
            result += this.characters[i]
        }
    }
    return result 
};

/**
 * @return {boolean}
 */
CombinationIterator.prototype.hasNext = function() {
    // mask cannot iterate if there are no more combinations 
    return this.maskInd < this.mask.length-1
};

Discussion and Conclusions

I want to explore the approach of iterating the next combination based on the previous combination mask. This is because when the constructor is run, it is doing all the computational work up front, and finding all the permutations.

There are C(n, k) (n choose k) combinations, where n is the length of characters and k is combinationLength. And the height of the tree formed by my search is k (because there are k characters in a valid string) so the breadth-first-search scales at O( k*C(n,k) ).

If we use the formula for calculating combinations, we get:

 k * C(n,k) = k *  n!/(k! * (n-k)!) 
            = n!/((k-1)! * (n-k)!)                  

We can reduce the time complexity of the constructor if we just generate the initial mask, and developed a formula to determine the next mask based on the previous.

I wrote the following pseudocode in my comments but did not settle on a way to consistently determine the next mask value. I realized that at some point, the ones that have been moved from the left all the way to the right would have to be reset back to a position on the left. However, the next 1 on the left would've been shifted once to the right.

Example for characters.length = 6 and combinationLength = 3:

    111000 110100 110010 110001 
    reset to 101100 ... 101001
    reset to 100110 ... 100101
    reset to 100011 ... 100011
    reset to 011100 ... 011001

For my next steps I will explore writing an algorithm that can determine the next mask value from the previous. Since it follows a logical progression it should be possible, but I need to come up with some valid conditional statements for determining when to "reset" some of the 1's from the right back to the left.