Concatenate the words to obtain a single word with the longest possible substring composed of a single letter

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 say as to obtain a single word with the longest possible sub-string composed of one particular letter. Find the length of such a sub-string.

Examples:

Given N=3 and words=[‘aabb’,’aaaa’,’bbab’], your function should return 6. One of the best concatenations is words[1]+words[0]+words[2]=’aaaaaabbbbab’. The longest sub-string is composed of the letter ‘a’ and its length is 6.
Given N=3 and words=[‘xxbxx’,’xbx’,’x’], your function should return 4. One of the best concatenations is words[0]+words[2]+words[1]=’xxbxxxxbx’. The longest sub-string is composed of letter ‘x’ and its length is 4.

I know I should not be posting the answer, But might help someone who is looking for a optimal solution.

class DailyCodingProblem4 {

    public static void main(String args[]) {
        String[] arr = { "aabb", "aaaa", "bbab" };
        int res = solution(arr);
        System.out.println(res);

        String[] arr2 = { "xxbxx", "xbx", "x" };
        res = solution(arr2);
        System.out.println(res);
    }

    private static int solution(String[] arr) {
        Map<Integer, Integer> prefix = new HashMap<>();
        Map<Integer, Integer> suffix = new HashMap<>();
        Map<Integer, Integer> both = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            String word = arr[i];
            int j = 1;
            while (j < word.length() && word.charAt(0) == word.charAt(j)) {
                j++;
            }
            int key = word.charAt(0);
            if (j == word.length()) {
                if (both.containsKey(key)) {
                    Integer temp = both.get(key);
                    if (j > temp) {
                        both.put(key, j);
                    }
                } else {
                    both.put(key, j);
                }
            } else {
                if (suffix.containsKey(key)) {
                    Integer temp = suffix.get(key);
                    if (j > temp) {
                        suffix.put(key, j);
                    }
                } else {
                    suffix.put(key, j);
                }

                j = word.length() - 1;

                while (j > 0 && word.charAt(word.length() - 1) == word.charAt(j - 1)) {
                    j--;
                }

                key = word.charAt(word.length() - 1);
                if (prefix.containsKey(key)) {
                    Integer temp = prefix.get(key);
                    if (word.length() - j > temp) {
                        prefix.put(key, word.length() - j);
                    }
                } else {
                    prefix.put(key, word.length() - j);
                }
            }
        }
        int res = 0;
        for (Integer key : prefix.keySet()) {
            if (suffix.containsKey(key)) {
                int temp = prefix.get(key) + suffix.get(key);
                if (temp > res) {
                    res = temp;
                }
            }

        }

        for (Integer key : suffix.keySet()) {
            if (prefix.containsKey(key)) {
                int temp = prefix.get(key) + suffix.get(key);
                if (temp > res) {
                    res = temp;
                }
            }

        }

        for (Integer key : both.keySet()) {
            if (prefix.containsKey(key)) {
                int temp = prefix.get(key) + both.get(key);
                if (temp > res) {
                    res = temp;
                }
            }
            if (suffix.containsKey(key)) {
                int temp = both.get(key) + suffix.get(key);
                if (temp > res) {
                    res = temp;
                }
            }
        }

        return res;
    }
}

Answer

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.

Advertisement

Answer