Find the longest common ancestor path per group in Java

Question

I’m trying to find the longest common ancestor for each group in the generic path info. Below is my input list of type String

[/Module1:path1/path2/path3[key1=value1]/path4/leaf1,
/Module1:path1/path2/path3[key1=value1]/path4/leaf2,
/Module1:path1/path2/path3[key1=value1]/path5/leaf1,
/Module1:path1/path2/path3[key2=value2]/path4/leaf1,
/Module1:path1/path2/path3[key2=value2]/path4/leaf2,    
/Module3:path1/path2/path3[key3=value33]/path4/leaf2,
/Module3:path1/path2/path3[key3=*]/path4/leaf2,
/Module4:path1/path2[key4=value1]/path3[key5=value1]/path4/leaf2,
/Module4:path1/path2[key4=value1]/path3[key5=*]/path4/leaf2,
/Module5:path1/path2/path3/path4/leaf1]

From the above list, I’m trying to find the longest common ancestor per group. Below are the conditions:

1. Group the longest common ancestor path per module.
2. Each path may or may not contain key/value-based filters (it may contain one or more key filters).
3. If the path has the same key and the same module, group them together and find the longest common ancestor path.
4. If the path has the same module but different keys, consider them as separate entries.
5. If the key value is specified as "*", treat it as applicable to all values. In this case, exclude key entries for that module and return the generic path.
6. Exclude the leaf nodes (which are always the last element when the path is split by "/").

The final output what I'm expecting for the above input is

   [/Module1:path1/path2/path3[key1=value1],    
    /Module1:path1/path2/path3[key2=value2]/path4,
    /Module3:path1/path2/path3[key3=*]/path4,
    /Module4:path1/path2[key4=value1]/path3[key5=*]/path4,
    /Module5:path1/path2/path3/path4]  

I've tried a couple of ways, and I can find the longest common ancestor path without considering the keys. However, including the keys is returning unexpected output. What is the best approach to solve this problem efficiently?

Below is my code to group by module and exclude the leaf values.

 private static Map<String, List<String>> groupByModuleName(List<String> paths) {
    Map<String, List<String>> moduleGroups = new HashMap<>();
    for (String path : paths) {
        String[] components = path.split("/");
        String moduleName = components[0] + "/" + components[1];
        String truncatedPath = String.join("/", Arrays.copyOf(components, components.length - 1));
        if (moduleGroups.containsKey(moduleName)) {
            List<String> pathInfo = moduleGroups.get(moduleName);
            pathInfo.add(truncatedPath);
            moduleGroups.put(moduleName, pathInfo);
        } else {
            List<String> pathInfo = new ArrayList<>();
            pathInfo.add(truncatedPath);
            moduleGroups.put(moduleName, pathInfo);
        }
    }
    return moduleGroups;
}

After Grouping, In findCommonAncestorForGroup method, My logic to calculate the longest common ancestor path per group.

    Map<String, List<String>> moduleGroups = groupByModuleName(paths);
    List<String> result = new ArrayList<>();
    for (Map.Entry<String, List<String>> entry : moduleGroups.entrySet()) {
        List<String> groupPaths = entry.getValue();
        String commonAncestor = findCommonAncestorForGroup(groupPaths);
        result.add(commonAncestor);
    }
    return result;

In the findCommonAncestorForGroup method, I have tried a couple of ways to get the expected output, but some other use cases are breaking. Do you have any suggestions on how to solve this problem efficiently?

Please note that the module and path names can be anything. I have used Module1, Module2, etc., just to simplify my query

Answer 1

First, you need to identify the groups. Each group is defined by a common module and a common key. So, it would make sense to create a Map<String, Map<String, List<String[]>> where the key of the outer Map would be the module name, the key of the inner Map would be the key and the elements of the String List would be the actual paths (splitted by /). So far so good.

Step 1: Make the main groups

Loop the paths and for each path see whether the Module is already in the outer Map and create it if not. Then see whether the item of this Module has the key as a key already.

Of course, Module is to the left of the first : and, if you split the right-hand-side by / and then loop the parts, you can find what the key is. So it will be clear which Module's key is and hence adding the item will be easy too.

At this point, don't worry about * as key, create it inside the Map, we'll return to that later.

Step 2: Handle the stars

Loop your outer Map and see which inner Map has a key of *. for those items, loop the other inner keys and add this * to them, so if you have a module and there is an item with a *, then you append this item to all groups of the module and then remove this *. If you have multiple paths with *, avoid adding one star to the other.

Step 3: Find the longest common paths

Since you have the groups sorted out, you can loop each module and nest an inner loop for each key, where you have splitted strings. See how many of the first splitted substrings of the first two are common and that will be c. Then compare the first c splitted substrings of the first and the third and decreasing c if there are less in common between the first and the third and proceed this way until you reach the end of the group. Knowing what c is you can infer the first c splitted substrings of any element in the group and glue them together with / as the separator to reach the result you expect.