Problem statement

Write the class CombinationIterator, which hands out the combinations of a set of letters one at a time, in lexicographical order:

• CombinationIterator(String characters, int combinationLength) receives a string of sorted, distinct lowercase letters and the length of the combinations to produce.
• String next() returns the next combination of combinationLength letters (each combination keeps the letters in their original order).
• boolean hasNext() returns true if a call to next would still produce a combination.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["CombinationIterator","next","hasNext","next","hasNext","next","hasNext"]
[["xyz",2],[],[],[],[],[],[]]
Output: [null,"xy",true,"xz",true,"yz",false]
Explanation: The combinations of two letters from xyz, in order, are xy, xz, yz. After the third one, hasNext is false.

Example 2

Input: ["CombinationIterator","hasNext","next","next","next","next"]
[["bdfg",3],[],[],[],[],[]]
Output: [null,true,"bdf","bdg","bfg","dfg"]
Explanation: Choosing three of b, d, f, g gives bdf, bdg, bfg, dfg — four combinations.

Constraints

• 1 <= combinationLength <= characters.length <= 15
• characters consists of distinct lowercase English letters, sorted ascending
• At most 10^4 calls are made to next and hasNext
• Every call to next is valid

Hints for Iterator for Combination

1. Hint 1

   Since the letters are sorted, a combination is just a set of increasing positions i0 < i1 < … < i(k-1), and lexicographic order on the strings is lexicographic order on the positions.

2. Hint 2

   Start from positions 0, 1, …, k-1. To get the next combination, find the rightmost position that can still move right.

3. Hint 3

   Position j can move while idx[j] < n - k + j (there must be room for the positions after it). Increase it by one and set every later position to the one before it plus one. If no position can move, the iteration is over.

How to solve Iterator for Combination

Generate combinations lazily from an array of k increasing positions, advancing it the way an odometer advances — rightmost movable digit first.

Approach

1. Store the letters, k, the positions idx = [0, 1, …, k-1] and a flag has = true.
2. next(): build the answer from the letters at idx, then advance: find the largest j with idx[j] < n - k + j.
3. If there is none, this was the last combination: set has = false. Otherwise do idx[j]++ and idx[t] = idx[t-1] + 1 for every t > j.
4. hasNext(): return has.

Why it works

The positions after j are all at their maximum (n - k + t), so the current combination is the largest one with this prefix idx[0..j]. The smallest combination greater than it must change position j, by the least amount — one step — and then take the smallest possible tail, the consecutive positions after it. Because the letters are sorted and distinct, the order of position arrays is exactly the order of the strings.

Complexity

• Time — O(k) per call
• Space — O(k)

Pitfalls

• Precomputing every combination works for n ≤ 15 (at most 6,435) but wastes memory and time when few are asked for.
• The bound for position j is n - k + j, not n - 1: later positions need room after it.
• hasNext must be decided after advancing; computing it from the combination about to be returned is off by one.

Reference solution

Python

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.chars = characters
        self.k = combinationLength
        self.idx = list(range(combinationLength))
        self.has = True

    def next(self) -> str:
        chars, k, idx = self.chars, self.k, self.idx
        s = "".join(chars[i] for i in idx)
        j = k - 1
        while j >= 0 and idx[j] == len(chars) - k + j:  # already at its rightmost place
            j -= 1
        if j < 0:
            self.has = False
        else:
            idx[j] += 1
            for t in range(j + 1, k):
                idx[t] = idx[t - 1] + 1
        return s

    def hasNext(self) -> bool:
        return self.has

Java

class CombinationIterator {
    private String chars;
    private int k;
    private int[] idx;
    private boolean has = true;

    public CombinationIterator(String characters, int combinationLength) {
        chars = characters;
        k = combinationLength;
        idx = new int[k];
        for (int i = 0; i < k; i++) idx[i] = i;
    }

    public String next() {
        StringBuilder sb = new StringBuilder();
        for (int i : idx) sb.append(chars.charAt(i));
        int n = chars.length(), j = k - 1;
        while (j >= 0 && idx[j] == n - k + j) j--; // already at its rightmost place
        if (j < 0) has = false;
        else {
            idx[j]++;
            for (int t = j + 1; t < k; t++) idx[t] = idx[t - 1] + 1;
        }
        return sb.toString();
    }

    public boolean hasNext() {
        return has;
    }
}

C++

class CombinationIterator {
    string chars;
    int k;
    vector<int> idx;
    bool has = true;
public:
    CombinationIterator(string characters, int combinationLength) : chars(characters), k(combinationLength), idx(combinationLength) {
        for (int i = 0; i < k; i++) idx[i] = i;
    }

    string next() {
        string s;
        for (int i : idx) s += chars[i];
        int n = chars.size(), j = k - 1;
        while (j >= 0 && idx[j] == n - k + j) j--; // already at its rightmost place
        if (j < 0) has = false;
        else {
            idx[j]++;
            for (int t = j + 1; t < k; t++) idx[t] = idx[t - 1] + 1;
        }
        return s;
    }

    bool hasNext() {
        return has;
    }
};

JavaScript

var CombinationIterator = function(characters, combinationLength) {
    this.chars = characters;
    this.k = combinationLength;
    this.idx = [];
    for (var i = 0; i < combinationLength; i++) this.idx.push(i);
    this.has = true;
};

CombinationIterator.prototype.next = function() {
    var idx = this.idx, k = this.k, n = this.chars.length, s = "";
    for (var i = 0; i < k; i++) s += this.chars[idx[i]];
    var j = k - 1;
    while (j >= 0 && idx[j] === n - k + j) j--; // already at its rightmost place
    if (j < 0) this.has = false;
    else {
        idx[j]++;
        for (var t = j + 1; t < k; t++) idx[t] = idx[t - 1] + 1;
    }
    return s;
};

CombinationIterator.prototype.hasNext = function() {
    return this.has;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium
• Design Add and Search Words Data Structure Medium