LeetCode 1286: Iterator for Combination Solution

Master LeetCode problem 1286 (Iterator for Combination), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1286. Iterator for Combination

Medium

String Backtracking Design Iterator

Problem Explanation

Explanation

To solve this problem, we can use a backtracking approach. We can generate all combinations of length combinationLength in lexicographical order by exploring all possible combinations starting from the first character and moving forward recursively. We maintain a current combination state and update it as we move forward.

Algorithm:

Initialize the variables current to store the current combination, characters to store the input characters, and n to store the length of the input characters.
Implement the hasNext function to check if there is a next combination by comparing the length of the current combination with the required combinationLength.
Implement the next function to generate the next combination by recursively exploring all possible combinations.
Use backtracking to explore all combinations in lexicographical order.

Time Complexity:

The time complexity for generating the next combination and checking if there is a next combination is O(1) on average.

Space Complexity:

The space complexity is O(n) where n is the length of the input characters.

Solution Code

class CombinationIterator {
    private String characters;
    private int combinationLength;
    private String current;
    
    public CombinationIterator(String characters, int combinationLength) {
        this.characters = characters;
        this.combinationLength = combinationLength;
        this.current = characters.substring(0, combinationLength);
    }
    
    public String next() {
        String result = current;
        int i = combinationLength - 1;
        while (i >= 0 && current.charAt(i) == characters.charAt(characters.length() - combinationLength + i)) {
            i--;
        }
        if (i < 0) {
            current = "";
        } else {
            int index = characters.indexOf(current.charAt(i));
            current = current.substring(0, i) + characters.substring(index + 1, index + 2 + i);
        }
        return result;
    }
    
    public boolean hasNext() {
        return !current.equals("");
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1286 (Iterator for Combination)?

This page provides optimized solutions for LeetCode problem 1286 (Iterator for Combination) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1286 (Iterator for Combination)?

The time complexity for LeetCode 1286 (Iterator for Combination) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1286 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1286 in Java, C++, or Python.

Back to LeetCode Solutions