Find the longest sub string of a word after concatenation of given words array

Question

An Array of N words is given. Each word consists of small letters ('a'-'z'). Our goal is to concatenate the words in such a way as to obtain a single word with longest possible substring composed of one particular letter. Find the length of such substring.

Example 1: words = ["aaba", "aaaa", "bbab"] -> maxSubstring=6 of letter a, from the concatenated word = words[1] + words[0] + words[2] = "aaaaaababbab"

Example 2: words = ["xxbxx", "xbx", "x"] -> maxSubstring=4 of letter x, from the concatenated word = words[0] + words[2] + words[1] = "xxbxxxxbx"

My current implementation uses brute force: find all combinations of words, and calculate the max sub-string. Complexity is \$O(2^n)\$.

I'm looking for better ideas to reduce the time complexity.

class candiateCode{
    static Integer max = Integer.MIN_VALUE;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        String[] arr = new String[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextLine();

        }

        findCombi(arr, N, "", new HashMap<Integer, Boolean>());

        System.out.println(max);

    }

    private static void findCombi(String[] arr, int n, String prefix, Map<Integer, Boolean> map) {
        if (n == 0) {
            calculateMaxChar(prefix);
        }
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(i)) {
                Map<Integer, Boolean> map2 = new HashMap<>(map);
                map2.put(i, true);
                findCombi(arr, n - 1, prefix.concat(arr[i]), map2);
            }

        }
    }

    static void calculateMaxChar(String str) {
        Integer max1 = 1;
        Integer curr = 1;
        char ch = str.charAt(0);
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i) == ch) {
                curr++;
            } else {
                ch = str.charAt(i);
                curr = 1;
            }
            if (max1 < curr)
                max1 = curr;

        }
        if (max1 > max)
            max = max1;

    }
}

Answer 1

Think of encapsulation and responsibilities

The main method parses the input and uses this piece of code to compute and print the answer:

findCombi(arr, N, "", new HashMap<Integer, Boolean>());

System.out.println(max);

This is ugly in many ways:

• Where does the value of max come from? It's a global variable, its value gets set as a side effect of the call to findCombi. Try to organize code in a way to avoid side effects.

• What are all those parameters passed to findCombi? They are low-level implementation details of findCombi. They should not be exposed outside that function. The main method shouldn't have to know how the solution is computed. It has the inputs (the array of words), it should pass just that to a function, and get an int back as the answer.

• The parameter N is redundant, thanks to the .length field of arrays in Java.

This is what the snippet should have looked like:

int solution = findLongestSubstringCombination(arr);

There are no unnecessary parameters, and no side effects needed.

Answer 2

Here is a new logic I came up with For each letter, you need to know:

the total length of words consisting entirely of that letter; the words with the longest and second-longest prefix of that letter; and the words with the longest and second-longest suffix of that letter Since each word goes in at most 2 of these groups, determined by the letters it starts and ends with, you can figure this all out in O(N) time Will post the working snippet shortly