Print unique subset in lexicographic order

Question

For my string input "aaa" I want the answer to be

[[],[a],[a,a],[a,a,a]]

My code:

import java.util.*;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        String a = "aaa";

        char arr[] = a.toCharArray();
        Arrays.sort(arr);
        List<List<Character>> big = new ArrayList<List<Character>>();

        subset(arr, 0, big, new ArrayList<Character>(), true);

        System.out.println(big);
    }

    static void subset(char arr[], int count, List<List<Character>> big,
                       List<Character> temp, boolean flag) {
        if (count == arr.length) {
            big.add(new ArrayList<Character>(temp));
            return;
        }
        if (flag == false && arr[count] == arr[count - 1]) {
            // logic for unique subset
            subset(arr, count + 1, big, temp, false);     
        } else {
            temp.add(arr[count]);
            subset(arr, count + 1, big, temp, true);
            temp.remove(temp.size() - 1);
            subset(arr, count + 1, big, temp, false);
        }
    }
}

This code gave me this output:

[[a, a, a], [a, a], [a], []]

but I want this as: Required output:

[[],[a],[a,a],[a,a,a]]

Also the logic which I wrote for getting unique subset can also be done using a collection like TreeSet and HashSet. I tried using TreeSet the answer was in sorted order and unique subset but with some extra commas. It would be really helpful if someone would solve my both problems.

dreamcrash · Answer 1 · 2021-03-28T17:45:51.407

You can use TreeSet, and add a custom comparator:

Set<List<Character>> big = new TreeSet<>((l1, l2) -> {
    if (l1.size() != l2.size()) {
        return l1.size() - l2.size();
    }
    for (int i = 0; i < l1.size(); i++) {
        int strCmp = l1.get(i).compareTo(l2.get(i));
        if (strCmp != 0) {
            return strCmp;
        }
    }
    return 0;
});

And use replaceAll("\\s+","") to remove the extra spaces.

Everything put together:

import java.util.*;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        String a = "aaa";
        char[] arr = a.toCharArray();
        Arrays.sort(arr);
        Set<List<Character>> big = new TreeSet<>((l1, l2) -> {
            if (l1.size() != l2.size()) {
                return l1.size() - l2.size();
            }
            for (int i = 0; i < l1.size(); i++) {
                int strCmp = l1.get(i).compareTo(l2.get(i));
                if (strCmp != 0) {
                    return strCmp;
                }
            }
            return 0;
        });

        subset(arr, 0, big, new ArrayList<Character>(), true);
        custom_printing(big);
    }

    public static void custom_printing(Set<List<Character>> big){
        System.out.println(big.toString().replaceAll("\\s+",""));
    }

    static void subset(char[] arr, int count, Set<List<Character>> big, List<Character> temp, boolean flag) {
        if (count == arr.length) {
            big.add(new ArrayList<>(temp));
        }
        else if (!flag && arr[count] == arr[count - 1]) {
            // logic for unique subset
            subset(arr, count + 1, big, temp, false);
        } else {
            temp.add(arr[count]);
            subset(arr, count + 1, big, temp, true);
            temp.remove(temp.size() - 1);
            subset(arr, count + 1, big, temp, false);
        }
    }
}

Output:

[[],[a],[a,a],[a,a,a]]

Or (has pointed in the comments) you can use Collections.reverse combined with our custom_printing method:

public class Main {
    public static void main(String[] args) {
        String a = "aaa";

        char[] arr = a.toCharArray();
        Arrays.sort(arr);
        List<List<Character>> big = new ArrayList<>();

        subset(arr, 0, big, new ArrayList<>(), true);
        Collections.reverse(big);
        custom_printing(big);
    }

    public static void custom_printing(List<List<Character>> big){
        System.out.println(big.toString().replaceAll("\\s+",""));
    }

    static void subset(char[] arr, int count, List<List<Character>> big,
                       List<Character> temp, boolean flag) {
        if (count == arr.length) {
            big.add(new ArrayList<Character>(temp));
            return;
        }
        if (!flag && arr[count] == arr[count - 1]) {
            // logic for unique subset
            subset(arr, count + 1, big, temp, false);
        } else {
            temp.add(arr[count]);
            subset(arr, count + 1, big, temp, true);
            temp.remove(temp.size() - 1);
            subset(arr, count + 1, big, temp, false);
        }
    }

Output:

[[],[a],[a,a],[a,a,a]]

score 1 · Answer 2 · answered Mar 28 '21 at 17:54

The solution is to use the overloaded method List#add(int, T) instead of List#add(T). That way, your items will always be inserted at the beginning of the list instead of the end.

You can replace this line

big.add(new ArrayList<Character>(temp));

By the following

big.add(0, new ArrayList<Character>(temp));

And you'll get the following result

[[], [a], [a, a], [a, a, a]]

Print unique subset in lexicographic order

2 Answers2