1286. Iterator for Combination LeetCode Solution

In this guide, you will get 1286. Iterator for Combination LeetCode Solution with the best time and space complexity. The solution to Iterator for Combination problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Iterator for Combination solution in C++
Iterator for Combination solution in Java
Iterator for Combination solution in Python
Additional Resources

1286. Iterator for Combination LeetCode Solution image

Problem Statement of Iterator for Combination

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 104 calls will be made to next and hasNext.
It is guaranteed that all calls of the function next are valid.

Complexity Analysis

Time Complexity: O(n \cdot 2^n)
Space Complexity:

1286. Iterator for Combination LeetCode Solution in C++

class CombinationIterator {
  public CombinationIterator(String characters, int combinationLength) {
    final int n = characters.length();
    final int k = combinationLength;

    // Generate bitmasks from 0..00 to 1..11
    for (int mask = 0; mask < 1 << n; mask++) {
      // Use bitmasks with k 1-bits
      if (Integer.bitCount(mask) == k) {
        // Convert bitmask into combination
        // 111 --> "abc", 000 --> ""
        // 110 --> "ab", 101 --> "ac", 011 --> "bc"
        StringBuilder curr = new StringBuilder();
        for (int j = 0; j < n; j++) {
          if ((mask & (1 << n - j - 1)) != 0) {
            curr.append(characters.charAt(j));
          }
        }
        combinations.push(curr.toString());
      }
    }
  }

  public String next() {
    return combinations.pop();
  }

  public boolean hasNext() {
    return (!combinations.isEmpty());
  }

  private Deque<String> combinations = new ArrayDeque<String>();
}
/* code provided by PROGIEZ */