This problem asks you to design a data structure that generates combinations of characters from a given string, in lexicographical order, one at a time, through two methods:

You must implement:

CombinationIterator(String characters, int combinationLength)
next()  → returns next combination string
hasNext() → returns true if more combinations remain

Example:

Input:
characters = "abc", combinationLength = 2
Output sequence:
"ab", "ac", "bc"

---

Problem Understanding

Given:

• a sorted string of distinct lowercase characters
• a target combination length

You must:

• generate all combinations of size combinationLength
• return them one by one in lexicographical order
• support repeated calls to next()
• ensure hasNext() accurately reports availability

Important notes:

• Order must follow character order, not permutation
• Combinations are static — no mutation during iteration
• Efficiency matters because number of calls may be high

---

Logic Explained in Simple English

To solve this problem cleanly, think about it like this:

1. We need all possible combinations of characters of a given length.
2. These combinations must be generated in sorted order.
3. Instead of computing a new combination on every call,
   the easiest method is to precompute all combinations once.
4. Store them in a list.
5. Maintain an index pointer.
6. Each call to next() returns the next stored combination.
7. Each call to hasNext() checks whether the pointer reached the end.

Why this works:

• Characters are already in sorted order
• Combination generation ensures correct sequence
• Lookup becomes O(1)
• Generation cost happens only once

---

Step-by-Step Approach

Step 1 — Generate combinations

Use backtracking:

• Build combinations character by character
• When length reached, store result
• Recursively explore next positions

Step 2 — Store all combinations in a list

Step 3 — Maintain current index

• Start at index 0
• next() returns list[index] and increments
• hasNext() checks index < list.size()

This approach is simple, predictable, and efficient for LeetCode constraints.

---

Java Implementation

class CombinationIterator {

    private List<String> combinations;
    private int index;

    public CombinationIterator(String characters, int combinationLength) {
        combinations = new ArrayList<>();
        generateCombinations(characters, combinationLength, 0, new StringBuilder());
        index = 0;
    }

    private void generateCombinations(String chars, int length, int start, StringBuilder current) {
        if (current.length() == length) {
            combinations.add(current.toString());
            return;
        }

        for (int i = start; i < chars.length(); i++) {
            current.append(chars.charAt(i));
            generateCombinations(chars, length, i + 1, current);
            current.deleteCharAt(current.length() - 1);
        }
    }

    public String next() {
        return combinations.get(index++);
    }

    public boolean hasNext() {
        return index < combinations.size();
    }
}

---

Dry Run Example

Input:

characters = "abc"
combinationLength = 2

Combination Generation

Start: “”

• choose ‘a’
  • choose ‘b’ → “ab” stored
  • choose ‘c’ → “ac” stored
• choose ‘b’
  • choose ‘c’ → “bc” stored
• choose ‘c’
  • cannot reach length 2

Generated list:

["ab", "ac", "bc"]

Iteration Calls

Call 1:

next() → "ab"
hasNext() → true

Call 2:

next() → "ac"
hasNext() → true

Call 3:

next() → "bc"
hasNext() → false

---

Time and Space Complexity

Precomputation Time

Number of combinations:

C(n, k)

So total generation time is:

O(C(n, k) * k)

next() Time

O(1)

hasNext() Time

O(1)

Space Complexity

O(C(n, k) * k)

for storing all combinations

---

Common Mistakes and How to Avoid Them

Mistake 1: Generating permutations instead of combinations

Combinations never reorder characters.

Mistake 2: Trying to compute next combination on the fly

Makes logic complicated and error-prone.

Mistake 3: Ignoring lexicographical order

Must follow character order strictly.

Mistake 4: Modifying characters during iteration

Input string must be treated as fixed.

Mistake 5: Mismanaging iterator index

Ensure index increments only in next()