1286. Iterator for Combination

MediumDesignStringBacktrackingIterator
Leetcode Link

Problem Description

The CombinationIterator class is designed to handle combinations of a given string. The problem is defined with three requirements:

  1. The class must be initialized with a string characters consisting of sorted distinct lowercase English letters and an integer combinationLength which specifies the length of the combinations to be formed.

  2. A next() function that, when called, returns the next combination of the specified length combinationLength in lexicographical order.

  3. A hasNext() function that returns true if there are more combinations that can be generated and false if no more combinations are available.

The challenges in solving this problem include managing the generation of combinations in the proper order without actual generation of all combinations at once which would be inefficient, as well as determining when no more combinations are available.

Intuition

To arrive at the solution, the key is to implement an efficient way of generating the next lexicographical combination without having to pre-compute all possible combinations.

The solution code uses bit manipulation to achieve this. Here's how the solution operates:

  1. The string characters is reversed and each character is associated with a bit in an integer self.curr. Initially, self.curr is set to 2^len(characters) - 1, which means all the bits are set and then it will decrease with each call to next().

  2. The next() function looks for the current combination by checking if there are self.size bits set in self.curr (indicating the current combination's characters). If not, it keeps decrementing self.curr until there are the correct number of bits set, indicating the next valid combination.

  3. Once a valid combination is found, the corresponding characters are extracted and joined to form the next lexicographical combination string.

  4. The hasNext() function also decrements self.curr while invalid combinations are found (those not having the exact number of desired bits set), checking afterward if there are any valid combinations left (by checking if self.curr is greater than or equal to 0).

Note: self.curr.bit_count() is a method that returns the number of set bits (ones) in self.curr, which is used to determine if the current bit configuration corresponds to the desired combinationLength.

Intuitively, we are navigating a binary tree, where each node represents a combination. Moving to the next combination is done by traversing the tree in a specific order, in this case, lexicographical order, which correlates to the decreasing numerical value of the binary representation of self.curr.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The CombinationIterator harnesses the efficiency of bit manipulation and bitwise operations to deal with combination generation. Here's an in-depth look into how the solution's implementation handles the process:

  1. Data Structure: The class does not use an actual data structure like an array or list to store combinations. Instead, it relies on an integer (self.curr) to represent the combinations as sets of bits, with each bit corresponding to whether a character in the string is included (1) or not (2). The string characters are reversed in (self.cs) to facilitate the formation of combinations in lexicographical order when bits are right shifted during combination extraction.

  2. Initialization:

    • self.curr is initialized to (1 << len(characters)) - 1, which sets all bits to 1, to the length of characters. This represents the full set of characters.
    • self.size holds the required combination length.
    • self.cs holds the reversed string of characters for easier iteration from least significant bit to most significant bit in the context of the combination string.

  3. The next() Function:

    • The while loop decrements self.curr until it finds a number whose binary representation contains exactly self.size number of 1 bits.
    • The for loop iterates through the bits of self.curr. Whenever it encounters a set bit, it appends the corresponding character from self.cs to the ans list.
    • Finally, the current combination (ans) is updated by reversing and joining to form the string before self.curr is decremented to move to the next combination.

  4. The hasNext() Function:

    • Similar to next(), hasNext() uses a while loop to decrement self.curr until the number of bits set matches self.size.
    • Then, it simply checks whether self.curr is non-negative, meaning there is at least one more combination remaining.

  5. Algorithm: The algorithm efficiently generates the next combination on-the-fly without maintaining a collection of all combinations which could be computationally expensive. It uses a binary counter decreasing from the largest possible value and ensures only those binary numbers with the correct number of 1 bits are accepted as valid combinations.

  6. Performance: This implementation exhibits both time and space efficiency. It does not compute all combinations upfront, thereby saving on space. The time complexity of the next() method is O(n), where n is the length of the characters string, and is based on the number of bits that need to be checked. The hasNext() method runs in the same complexity due to the similar while loop.

By utilizing bit manipulation and bitwise operations, the solution effectively iterates over the combinations in lexicographical order without pre-computing an extensive list of all possible combinations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have the following input:

characters = "abc", and combinationLength = 2.

The CombinationIterator will produce combinations of the 2 letters from the 3 letter input string in lexicographical order.

Initialization:

  • self.curr is initialized to (1 << 3) - 1, which is 7 in binary (111). This represents the full set of characters 'abc'.
  • self.size is set to 2 because we want combinations of two characters.
  • self.cs stores the reversed string "cba" so we start extracting combinations from right to left in terms of significance.

The next() Function:

  • We call next(), the algorithm starts by checking if self.curr, which is 111 in binary or 7 in decimal, has exactly 2 bits set. In this case, it does, so it proceeds to create the next combination.
  • The combination "ab" (110 in binary) is derived by including the first and second characters of the reversed string, which are "b" and "c" in the original string, thus forming the combination "bc".
  • self.curr is decremented to 110 in binary or 6 in decimal after forming the first combination.

The hasNext() Function:

  • After calling next() once, we can call hasNext() to see if there's another combination. Since self.curr is 6 (110 in binary) and can be decremented further to find another combination with two 1 bits, hasNext() will return true.

Subsequent Calls to next() and hasNext():

  • We call next() again, and this time, self.curr = 6 (110). It has exactly 2 bits set, so it's a valid combination. The next combination, "ac" (101 in binary), is formed by including the first and third characters of the reversed string ("c" and "a" in the original string), resulting in "ca".
  • self.curr is then decremented to 101 in binary or 5 in decimal.
  • If we were to call hasNext() now, it would return true again since self.curr can still be decremented to the next valid combination.
  • The next call to next() would decrement self.curr to 011 (3 in decimal), corresponding to the combination "bc" in the original string, which translates to "cb" in the reversed string.
  • Once self.curr reaches a value that doesn't have 2 bits set after decrementing (in this case, when it's less than 3), calling next() would not yield any more combinations, and hasNext() would return false.

This process will iterate through all the combinations ("bc", "ca", "ab") without pre-calculated list and in a memory-efficient way, only computing the next combination when next() is called.

Solution Implementation

1class CombinationIterator:
2    def __init__(self, characters: str, combination_length: int):
3        # Set the initial value of the bit mask to have all bits set, up to the length of `characters`.
4        self.current_mask = (1 << len(characters)) - 1
5        # Set the required size of the combination.
6        self.combination_size = combination_length
7        # Reverse the characters to align with the bitwise representation.
8        self.characters_reversed = characters[::-1]
9
10    def next(self) -> str:
11        # Find the next mask with the correct number of bits set (i.e., the correct combination size).
12        while self.current_mask >= 0 and bin(self.current_mask).count('1') != self.combination_size:
13            self.current_mask -= 1
14      
15        # Use the mask to select characters and form the next combination.
16        combination = []
17        for i in range(len(self.characters_reversed)):
18            # If the ith bit of the mask is set, append the corresponding character.
19            if (self.current_mask >> i) & 1:
20                combination.append(self.characters_reversed[i])
21      
22        # Decrease the mask value to move to the 'previous' combination.
23        self.current_mask -= 1
24        # Return the combination as a string in the correct order.
25        return ''.join(combination[::-1])
26
27    def hasNext(self) -> bool:
28        # Check if there is another combination by verifying if a valid mask exists.
29        while self.current_mask >= 0 and bin(self.current_mask).count('1') != self.combination_size:
30            self.current_mask -= 1
31        # Return boolean value representing if a valid mask is available.
32        return self.current_mask >= 0
33
34# Example of how the CombinationIterator class would be instantiated and used:
35# obj = CombinationIterator(characters, combination_length)
36# param_1 = obj.next()
37# param_2 = obj.hasNext()
38
1class CombinationIterator {
2
3    private int currentCombinationBitMask;
4    private int combinationLength;
5    private char[] charactersArray;
6
7    // Constructor for the iterator.
8    // Prepares the initial combination and reverses the input characters to use with bitwise manipulation
9    public CombinationIterator(String characters, int combinationLength) {
10        int n = characters.length();
11        // Initialize a bitmask with least significant "n" bits set to 1
12        currentCombinationBitMask = (1 << n) - 1;  
13        this.combinationLength = combinationLength;
14        charactersArray = new char[n];
15      
16        // Reverse the characters to align with the bit positions
17        for (int i = 0; i < n; ++i) {
18            charactersArray[i] = characters.charAt(n - i - 1);
19        }
20    }
21
22    // Generates the next combination in lexicographical order.
23    public String next() {
24        // Find the next bitmask representing a valid combination with the required number of bits set
25        while (currentCombinationBitMask >= 0 && Integer.bitCount(currentCombinationBitMask) != combinationLength) {
26            --currentCombinationBitMask;
27        }
28      
29        // Build the next combination based on the current bitmask
30        StringBuilder nextCombination = new StringBuilder();
31        for (int i = 0; i < charactersArray.length; ++i) {
32            // Check if the i-th bit of currentCombinationBitMask is set
33            if (((currentCombinationBitMask >> i) & 1) == 1) {
34                nextCombination.append(charactersArray[i]);
35            }
36        }
37      
38        // Prepare for the next call to next() by decrementing the bitmask
39        --currentCombinationBitMask;
40      
41        // Reverse the built combination string as the charactersArray was initially reversed
42        return nextCombination.reverse().toString();
43    }
44
45    // Checks if there are additional combinations.
46    public boolean hasNext() {
47        // Check if the next valid combination exists
48        while (currentCombinationBitMask >= 0 && Integer.bitCount(currentCombinationBitMask) != combinationLength) {
49            --currentCombinationBitMask;
50        }
51        return currentCombinationBitMask >= 0;
52    }
53}
54
1#include <algorithm>
2#include <string>
3
4class CombinationIterator {
5public:
6    // The bit mask representing the current combination
7    int currentMask;
8    // The reversed input string to easily use with bitwise operations
9    string charactersReversed;
10    // The desired length of combinations
11    int combinationLength;
12
13    // Constructor to initialize the iterator with a string and combination length
14    CombinationIterator(string characters, int combLength)
15        : combinationLength(combLength) {
16        int n = characters.size();
17        // Initialize the bitmask with all 1's for the size of the characters
18        currentMask = (1 << n) - 1;
19        // Reverse the characters to align with the bitmask's LSB to the first character
20        reverse(characters.begin(), characters.end());
21        charactersReversed = characters;
22    }
23
24    // Returns the next combination in lexicographical order
25    string next() {
26        // Find the next valid combination with the required number of 1's in the bitmask
27        while (currentMask >= 0 && __builtin_popcount(currentMask) != combinationLength)
28            --currentMask;
29      
30        string combination;
31        // Iterate over the characters and select the ones included in the current combination
32        for (int i = 0; i < charactersReversed.size(); ++i) {
33            if ((currentMask >> i) & 1) {
34                // Add character if the corresponding bit is set in the bitmask
35                combination += charactersReversed[i];
36            }
37        }
38        // Reverse the combination to maintain lexicographical order
39        reverse(combination.begin(), combination.end());
40        // Prepare bitmask for the next call to 'next'
41        --currentMask;
42        return combination;
43    }
44
45    // Check if there is a valid next combination
46    bool hasNext() {
47        // Find the next valid combination with the required number of 1's in the bitmask
48        while (currentMask >= 0 && __builtin_popcount(currentMask) != combinationLength)
49            --currentMask;
50        // If the bitmask is non-negative, there is a next combination
51        return currentMask >= 0;
52    }
53};
54
55/*
56 * How to use the CombinationIterator class:
57 * CombinationIterator* iterator = new CombinationIterator("abc", 2);
58 * string combination = iterator->next(); // returns "ab"
59 * bool has_next = iterator->hasNext(); // returns true if there is another combination
60 */
61
1function getNextBitmaskCombination(bitmask: number, combLength: number): number {
2    while (bitmask >= 0 && countSetBits(bitmask) !== combLength) {
3        --bitmask;
4    }
5    return bitmask;
6}
7
8// Transforms a bitmask into the corresponding combination string.
9function bitmaskToCombination(bitmask: number, reversed: string, combLength: number): string {
10    let combination = '';
11    for (let i = 0; i < reversed.length; ++i) {
12        if ((bitmask >> i) & 1) {
13            combination += reversed[i];
14        }
15    }
16    combination = combination.split('').reverse().join(''); // Reverse to maintain lexicographical order
17    return combination;
18}
19
20// Returns the number of set bits (1's) in a binary representation of a number.
21function countSetBits(num: number): number {
22    let count = 0;
23    while (num) {
24        count += num & 1;
25        num = num >> 1;
26    }
27    return count;
28}
29
30// The bit mask representing the current combination
31let currentMask: number;
32// The reversed input string to easily use with bitwise operations
33let charactersReversed: string;
34// The desired length of combinations
35let combinationLength: number;
36
37// Function to initialize the variables with a string and combination length
38function initialize(characters: string, combLength: number): void {
39    combinationLength = combLength;
40    const n = characters.length;
41    currentMask = (1 << n) - 1; // Initialize the bitmask with all 1's for the size of the characters
42    charactersReversed = characters.split('').reverse().join(''); // Reverse the characters
43}
44
45// Function to return the next combination in lexicographical order
46function nextCombination(): string {
47    currentMask = getNextBitmaskCombination(currentMask, combinationLength); // Get the next valid combination bitmask
48    let combination = '';
49    if (currentMask >= 0) {
50        combination = bitmaskToCombination(currentMask, charactersReversed, combinationLength);
51    }
52    --currentMask; // Prepare bitmask for the next call
53    return combination;
54}
55
56// Function to check if there is a valid next combination
57function hasNextCombination(): boolean {
58    const nextMask = getNextBitmaskCombination(currentMask, combinationLength); // Check for the next valid combination
59    return nextMask >= 0; // Return true if the next combination exists
60}
61
62// Example usage:
63// initialize("abc", 2);
64// const combination = nextCombination(); // Should return "ab"
65// const has_next = hasNextCombination(); // Should return true if there is another combination
66
Not Sure What to Study? Take the 2-min Quiz：

A heap is a ...?

Time and Space Complexity

The given code defines a class CombinationIterator which is responsible for iterating over all combinations of a specific length from the given string. Here, we analyze the time complexity and space complexity for methods next and hasNext.

next method:

  • Time Complexity: The worst-case time complexity of the next method can be considered as O(N) where N is the length of the characters string. This occurs because in the worst case, one might have to traverse all the bits to find the right combination that matches the required combinationLength. Besides, the construction of the combination itself takes O(N) in the worst case (where all characters are included in the combination).
  • Space Complexity: The next method uses ans list to store the current combination, so in the worst case where the combination includes all characters, the space complexity will be O(N).

hasNext method:

  • Time Complexity: The hasNext method internally performs the same process as the next method minus the part where the actual combination is constructed. Thus, it has a time complexity of O(N) for the same reasons as the next method since it potentially needs to check every bit of curr.
  • Space Complexity: The hasNext method does not use any additional space that scales with the input size, hence the space complexity is O(1) as it updates the curr value only.

Overall:

The overall space complexity for the CombinationIterator class is O(N) due to the storage of the cs field which is the reversed characters string.

Note: bit_count() is a method that returns the number of set bits (1s) in the integer. As of Python 3.10, this is a built-in method, and its time complexity could be considered O(1) on average, though it could vary based on the implementation. If bit_count() is not available in an earlier Python version, an equivalent method to count bits would have a time complexity of O(log(curr)) due to counting the bits in a number; however, log(curr) is bounded by N, it will not be larger than N and therefore is negligible in comparison to the cost of traversing the string itself.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫