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