Iterator for Combination

Medium

Asked by:

4 views

Topics:

Strings

Design the CombinationIterator class:

CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
next() Returns the next combination of length combinationLength in lexicographical order.
hasNext() Returns true if and only if there exists a next combination.

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

Constraints:

1 <= combinationLength <= characters.length <= 15
All the characters of characters are unique.
At most 10⁴ calls will be made to next and hasNext.
It is guaranteed that all calls of the function next are valid.

Try coding it in LeetCode

Iterator for Combination

Medium

Asked by:

4 views

Topics:

Strings

Design the CombinationIterator class:

CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
next() Returns the next combination of length combinationLength in lexicographical order.
hasNext() Returns true if and only if there exists a next combination.

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

Constraints:

1 <= combinationLength <= characters.length <= 15
All the characters of characters are unique.
At most 10⁴ calls will be made to next and hasNext.
It is guaranteed that all calls of the function next are valid.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `characters` and the value of `combinationLength`? What are the constraints on these values?
Can the input string `characters` contain duplicate characters? If so, how should the iterator handle them - should the combinations still be unique?
If `hasNext()` is called when no more combinations are available, should it always return `false`, or is there any specific behavior expected in such a case?
Is the input string `characters` guaranteed to be sorted in lexicographical order? If not, should the combinations returned by `next()` also be lexicographically sorted?
What should `next()` return if there are no more combinations available (i.e., `hasNext()` would return `false`)? Should it throw an exception, return null, or some other specific value?

Brute Force Solution

Approach

The brute force approach generates all possible combinations by systematically exploring every potential grouping. It checks each combination against the criteria to see if it's a valid solution. This continues until all possibilities are exhausted, guaranteeing that the valid combinations are discovered.

Here's how the algorithm would work step-by-step:

Start by considering the very first combination possible.
Create the combination, and store it somewhere.
Determine if that particular combination meets all requirements.
If it does not meet the requirements, discard it. It is not a valid solution.
Move on to the very next possible combination.
Repeat the process of creating the combination, storing it, and determining if it meets all requirements. Keep doing this until there are no more combinations left to consider.
You now have a list of all possible valid combinations.

Code Implementation

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.combinationLength = combinationLength
        self.combinations = []
        self.generate_combinations(0, "", 0)
        self.index = 0

    def generate_combinations(self, start_index: int, current_combination: str, current_length: int):
        # If a combination of the required length has been found, add it to results
        if current_length == self.combinationLength:
            self.combinations.append(current_combination)
            return

        # If the end of the input has been reached, backtrack.
        if start_index == len(self.characters):
            return

        # Explore including the current character
        self.generate_combinations(start_index + 1, current_combination + self.characters[start_index], current_length + 1)

        # Explore excluding the current character, find all combinations
        self.generate_combinations(start_index + 1, current_combination, current_length)

    def next(self) -> str:
        # Determine if there are any more combinations available.
        result = self.combinations[self.index]
        self.index += 1
        return result

    def hasNext(self) -> bool:
        return self.index < len(self.combinations)

Big(O) Analysis

Time Complexity

O(nCr) – The brute force approach generates all possible combinations of length r from a string of length n, where nCr represents the number of combinations. The algorithm iterates through each possible combination. For each combination generated, which takes O(1) time, the algorithm checks if it's valid. Since we are checking all possible combinations, the time complexity is directly proportional to the number of combinations, which is nCr (n choose r). Therefore, the overall time complexity is O(nCr).

Space Complexity

O(C(N, L)) – The algorithm stores each generated combination before checking its validity. Since we are creating and storing all possible combinations of length L from a string of length N, this requires space to store up to C(N, L) combinations, where C(N, L) represents the binomial coefficient (N choose L), indicating the number of combinations. Therefore, the auxiliary space is proportional to the number of generated combinations. Since the plain English explictly states that each combination is stored, this intermediate storage is what contributes to the space complexity, making it O(C(N, L)).

Optimal Solution

Approach

The challenge is to create combinations of elements one at a time. The optimal strategy focuses on maintaining the last generated combination and intelligently calculating the next one in sequence, without generating all possible combinations upfront.

Here's how the algorithm would work step-by-step:

Start with the first valid combination.
When asked for the next combination, find the rightmost element that can be incremented without exceeding the boundaries of the input.
Increment that element.
Reset all elements to the right of the incremented element to their smallest possible values, ensuring they maintain the combination's increasing order.
If no element can be incremented (meaning you've reached the last combination), indicate that there are no more combinations available.

Code Implementation

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.combinationLength = combinationLength
        self.currentCombination = ""
        self.indexList = list(range(combinationLength))

        # Initialize the first combination
        for i in range(combinationLength):
            self.currentCombination += characters[i]

    def next(self) -> str:
        result = self.currentCombination

        # Find the rightmost index to increment
        indexToIncrement = -1
        for i in range(self.combinationLength - 1, -1, -1):
            if self.indexList[i] < len(self.characters) - self.combinationLength + i:
                indexToIncrement = i
                break

        # If no such index exists, we've reached the end
        if indexToIncrement == -1:
            self.currentCombination = ""
            return result

        # Increment the index and update the current combination.
        self.indexList[indexToIncrement] += 1
        self.currentCombination = self.currentCombination[:indexToIncrement]
        self.currentCombination += self.characters[self.indexList[indexToIncrement]]

        # Reset the indices and characters to the right
        for i in range(indexToIncrement + 1, self.combinationLength):
            self.indexList[i] = self.indexList[i - 1] + 1
            self.currentCombination += self.characters[self.indexList[i]]

        return result

    def hasNext(self) -> bool:
        # Check if currentCombination is empty which indicates no more combinations
        return self.currentCombination != ""

Big(O) Analysis

Time Complexity

O(combinationLength) – The time complexity of the next() function is dominated by the loop that searches for the rightmost element to increment. This loop iterates at most combinationLength times, where combinationLength is the length of each combination. The resetting of elements to the right of the incremented element also takes at most combinationLength time. Therefore, the overall time complexity for the next() function is O(combinationLength).

Space Complexity

O(k) – The algorithm primarily uses a list (or array) of size k to store the current combination, where k is the desired length of each combination. This list is updated iteratively to generate the next combination. No other significant data structures are employed. Therefore, the auxiliary space complexity is directly proportional to k, representing the length of each combination generated.

Edge Cases

Case	How to Handle
Empty string characters is zero or negative.	Throw an IllegalArgumentException as a combination requires at least one character.
Combination length is greater than string length	Throw IllegalArgumentException or return an empty iterator since no combinations are possible.
Combination length is zero.	Throw an IllegalArgumentException because combinations of length zero are undefined or return an iterator with an empty string if this is the intended default behavior.
String contains duplicate characters.	The algorithm should still generate combinations correctly without considering multiplicity (treat duplicates as distinct).
String contains non-ASCII characters (e.g., Unicode).	Ensure the implementation handles Unicode correctly or restrict input string to ASCII.
Combination length is 1.	The iterator should return each character of the string individually.
String contains very long sequence and combination length is near String length.	Consider memory and time complexity of the backing data structure; iterative implementations are preferred to avoid stack overflow.
String length is at the allowed system maximum.	Be sure there are no memory overflow errors due to the string length.