import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        test_getBaseDns();
        test_isDescendantOf();
        test_isAncestorOf();
    }

    private static void test_getBaseDns() {
        System.out.println("===== test_getBaseDns =====");
        do_test_getBaseDns("A", "BA", "CBA");
        do_test_getBaseDns("A", "BA", "CBA", "D", "ED", "F", "IHG");
    }

    private static void do_test_getBaseDns(String... dns) {
        Set<String> baseDns = getBaseDns(Arrays.asList(dns));
        System.out.println("[" + String.join(",", dns) + "] -> {" + String.join(",", baseDns) + "}");
    }

	private static Set<String> getBaseDns(List<String> dns) {
		Set<String> baseDns = new HashSet<>();
		for (int i = 0; i < dns.size(); ++i) {
			String dn = dns.get(i);
            // Add dn if 1st -or- descendant baseDns were removed -or- no baseDn equals to or is an ancestor of dn
			if (i == 0 || baseDns.removeAll(getDescendants(baseDns, dn)) || !containsAncestor(baseDns, dn)) {
				baseDns.add(dn);
			}
		}
		return baseDns;
	}

    // every baseDns element baseDn which is an descendant of dn (baseDn > dn)
	private static Set<String> getDescendants(Set<String> baseDns, String dn) {
		Set<String> result = new HashSet<>();
		for (String baseDn : baseDns) {
			if (isDescendantOf(baseDn, dn, false)) {
				result.add(baseDn);
			}
		}
		return result;
	}

    private static void test_isDescendantOf() {
        System.out.println("===== test_isDescendantOf =====");
        List<String> s1s = new ArrayList<>();
        s1s.add("whatever");
        s1s.add("dc=mydb");
        s1s.add("o=myorg,dc=mydb");
        s1s.add("ou=myorgunit,o=myorg,dc=mydb");
        s1s.add("cn=myname,ou=myorgunit,o=myorg,dc=mydb");
        String s2 = "o=myorg,dc=mydb";
        System.out.println("s2: " + s2);
        for (String s1 : s1s) {
            System.out.println("s1: " + s1 + " -> " + isDescendantOf(s1, s2, true));
        }
    }

    private static boolean isDescendantOf(String s1, String s2, boolean allowEquals) {
        return s1.toLowerCase().endsWith(s2.toLowerCase()) && (allowEquals || s1.length() > s2.length());
    }

    // baseDns contains at least one baseDn which equals to or is an ancestor of dn (baseDn <= dn)
    private static boolean containsAncestor(Set<String> baseDns, String dn) {
		for (String baseDn : baseDns) {
			if (isAncestorOf(baseDn, dn, true)) {
				return true;
			}
		}
		return false;
	}

    private static void test_isAncestorOf() {
        System.out.println("===== test_isAncestorOf =====");
        List<String> s1s = new ArrayList<>();
        s1s.add("whatever");
        s1s.add("dc=mydb");
        s1s.add("o=myorg,dc=mydb");
        s1s.add("ou=myorgunit,o=myorg,dc=mydb");
        s1s.add("cn=myname,ou=myorgunit,o=myorg,dc=mydb");
        String s2 = "o=myorg,dc=mydb";
        System.out.println("s2: " + s2);
        for (String s1 : s1s) {
            System.out.println("s1: " + s1 + " -> " + isAncestorOf(s1, s2, true));
        }
    }

    private static boolean isAncestorOf(String s1, String s2, boolean allowEquals) {
        return s2.toLowerCase().endsWith(s1.toLowerCase()) && (allowEquals || s2.length() > s1.length());
    }
}