Concatenate words in such a way as to obtain the longest possible sub-string of the same letter

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 the longest possible sub-string composed of one particular letter. Find the length of such a sub-string.

• Examples:
  1. 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.
  2. 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.

 public 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);
                                 both.put(key, j + temp);

                        } 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;
            }
        }

Is there a better approach to solve the above problem? Is there something I can improve on?

Answer 1

I think I see a few bugs:

1. In the initial processing loop, your handling for the both case appears wrong. If you have words 'aa' and 'aaa', you would not replace the 2 with a 3, but rather you would add the 2+3 getting 5, since you can concatenate the words as 'aaaaa'.

2. In the prefix/suffix handling, there is the possibility that the same word would be the largest prefix and suffix, which is an impossibility. Consider a test case like this:

   String[] arr = { "xxbxxx", "xbx", "x" }; // note: xx(2)bxxx(3)
   res = solution(arr);
   

   What should res be? I believe you will compute the prefix['x'] as being 3, and the suffix['x'] as being 2, yielding an answer of 6. But the correct answer is 5, since you cannot use "xxbxxx" twice.

   (Note: This is a significant problem, since if true it will require you to significantly change how you are implementing your solution.)

3. In the final phase, computing results, your prefix and suffix loops ignore the possibility of a single winner. That is, prefix requires a suffix to win, and suffix requires a prefix to win. It does not allow for the possibility that a word like "xzzzzzzzzzz" could have a long enough (prefix|suffix) to just dominate the result.

4. The same is true for both: there is no acknowledgement of the possibility of a prefix+both+suffix.

And now here's some non-bug stuff:

You spend a lot of time checking if a map contains a given key. If you go through and count lines of code, it is probably the most expensive thing you do. (Not to mention that many of your bugs are around this area.) I think it would benefit you to set up your maps so that the keys were always present with a default value of zero. There are some proposed options in this SO question.

For a specific example, consider this:

if (both.containsKey(key)) {
    Integer temp = both.get(key);
    if (j > temp) {
        both.put(key, j);
    }
} else {
    both.put(key, j);
}

That could be rewritten as:

temp = both.getOrDefault(key, 0);
if (j > temp)
    both.put(key, j)

Which could be rewritten as:

if (j > both.getOrDefault(key, 0))
    both.put(key, j);

I also see code like this in a few places:

while (j < word.length() && word.charAt(0) == word.charAt(j)) {
    j++;
}
int key = word.charAt(0);

Why are you writing word.charAt(0) more than one time? Define the key above the loop, and make things shorter, clearer, and simpler:

int key = word.charAt(0);
while (j < word.length() && key == word.charAt(j)) {
    j++;
}

In your bottom section, you can remove a lot of that code using the map-with-default-value approach. The best answer is the one that has the largest total of prefix + both + suffix, where the default for any of them is zero. Also, res is a bad name. Try longest.

for (Integer key : prefix.keySet()) {
    longest_for_key = prefix.getOrDefault(key, 0) + both.getOrDefault(key, 0) + suffix.getOrDefault(key, 0);
    if (longest_for_key > longest)
        longest = longest_for_key;

}

You'll still have to do all three, since there might be a unique key in one of the maps with a dominant string. But as least the code is simpler.

Answer 2

Your code repeats in many places. Instead of using if (map.containsKey), you should make good use of Map.getOrDefault:

map.put(key, j + map.getOrDefault(key, 0));

That way you can convert many five-liners into one-liners.

Instead of the < operator just use Math.max, which leads to shorter code as well.

I don't understand the formatting of the code, especially why the methods are indented by 11 spaces. If there's no hidden meaning to it, let your IDE or editor format the code automatically.