Generate all possible strings in a range

Question

I need to generate all possible strings in a specific range. For example
Upper bound - aaa
Lowe bound - ccc

Also possible cases aab-caa , hhu - kkk , but not aaz - ccc Values should be

    aaa
    aab
    aac
    aba
    abb
    abc
    aca
    acb
    acc
    caa
    cab
    cac
    cca
    ccb
    ccc

I wrote such method but it doesn't work correctly, I have no idea how to do this correctly, it is too hard for me now to catch all possible cases, please help

 public static List<String> generateAllPossibleStrings(String start, String end) {
        if (start.length() != end.length()) {
            return null;
        }
        List<String> variants = new ArrayList<>();
        char startArray[] = start.toCharArray();
        char endArray[] = end.toCharArray();
        char currentArray[] = Arrays.copyOf(startArray, startArray.length);
        variants.add(new String(currentArray));
        for (int i = startArray.length - 1; i >= 0; i--) {
            while (currentArray[i] != endArray[i]) {
                currentArray[i]++;
                variants.add(new String(currentArray));
                for (int j = startArray.length - 1; j > i; j--) {
                    while (currentArray[j] != endArray[j]) {
                        currentArray[j]++;
                        variants.add(new String(currentArray));
                    }
                    currentArray[j] = startArray[j];

                }
            }
            currentArray[i] = startArray[i];
        }

        System.out.println(Arrays.toString(variants.toArray()));
        return variants;
    }

For the example above I got

[aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bca, caa, cab, cac, cba, cca]

As you can see some values are missing.

Please help to correct this method and make it work correctly or maybe it should be implemented as recursive method.

EXPLANATION

Why aaz - ccc is not possible because any character in lower bound (ccc) should be grater that corresponding character in the upper bound (aaz) in this example z is grater than c so this is incorrect.

Answer 1

EDIT : I might have misunderstood the problem, I thought the end string was above the start string in every position, but it doesn't seem to be the case from your other examples. Can you show what you are supposed to output on hhu-kkk, and explain what is wrong with aaz-ccc ?

EDIT2 : As I suspected, hhu-kkk is also an incorrect input (u>k), you should edit your question once again.

Consider the string as a number, which you increment.

When you go above the end string in one location, you put the letter of the start string instead and increment the next letter, just like an addition with carry.

Here's a modified version of your code. It now also checks that the two strings satisfy all the properties you describe (which shouldn't be necessary, if the function is used correctly).

public static List<String> generateAllPossibleStrings(String start, String end) {
    if(start==null||end==null)
        return null;
    if (start.length() != end.length())
        return null;
    int n = start.length();
    List<String> variants = new ArrayList<>();
    char startArray[] = start.toCharArray();
    char endArray[] = end.toCharArray();
    char currentArray[] = Arrays.copyOf(startArray, startArray.length);
    variants.add(new String(currentArray));

    //We check if the start string is really above the end string as specified
    //We output an empty string if it is not the case
    boolean possible = true;
    for(int i = 0; i<n; i++)
        possible = possible && (startArray[i]<=endArray[i]);
    if (!possible)
        return variants;


    while(!end.equals(new String(currentArray))){
        currentArray[n-1]+=1;
        int i = n-1;
        while(currentArray[i]>endArray[i]){
            currentArray[i]=startArray[i];
            i--;
            currentArray[i]++;
        }
        variants.add(new String(currentArray));
    }

    System.out.println(Arrays.toString(variants.toArray()));
    return variants;
}

Answer 2

I would use single responsibility principle, split implementation onto small clear methods and use recursion

import java.util.ArrayList;
import java.util.List;

public final class Permutations {

    public static List<String> generate(String begin, String end) {
        List<String> result = new ArrayList<>();

        String current = begin;
        while (true) {
            result.add(current);
            if (current.equals(end))
                break;
            current = getNextPermutation(current, end);
        }

        return result;
    }

    private static String getNextPermutation(String current, String end) {
        char[] candidate = current.toCharArray();
        createNextPermutation(candidate, current.length()-1, end);
        return String.valueOf(candidate);
    }

    private static void createNextPermutation(char[] candidate, int index, String end) {
        char c = getNextChar(candidate[index]);
        if (c > end.charAt(index)) {
            candidate[index] = 'a';
            createNextPermutation(candidate, index-1, end);
        }
        else {
            candidate[index] = c;
        }
    }

    private static char getNextChar(char c) {
        return (char)(c + 1);
    }
}