-
Notifications
You must be signed in to change notification settings - Fork 2
/
MaxLengthOfConcatenatedStringWithUniqueCharacters.java
82 lines (71 loc) · 2.18 KB
/
MaxLengthOfConcatenatedStringWithUniqueCharacters.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package Leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author kalpak
*
* Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.
*
* Return the maximum possible length of s.
*
*
*
* Example 1:
*
* Input: arr = ["un","iq","ue"]
* Output: 4
* Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
* Maximum length is 4.
* Example 2:
*
* Input: arr = ["cha","r","act","ers"]
* Output: 6
* Explanation: Possible solutions are "chaers" and "acters".
* Example 3:
*
* Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
* Output: 26
*
*
* Constraints:
*
* 1 <= arr.length <= 16
* 1 <= arr[i].length <= 26
* arr[i] contains only lower case English letters.
*
*/
public class MaxLengthOfConcatenatedStringWithUniqueCharacters {
public static int maxLength(List<String> arr) {
int[] result = new int[1];
findMaxUniqueLength(arr, 0, "", result);
return result[0];
}
private static void findMaxUniqueLength(List<String> arr, int index, String current, int[] result) {
if(index == arr.size() && getUniqueCharCount(current) > result[0]) {
result[0] = current.length();
return;
}
if(index == arr.size())
return;
findMaxUniqueLength(arr, index + 1, current, result);
findMaxUniqueLength(arr, index + 1, current + arr.get(index), result);
}
// check if a string made of unique string.
// If so, then return the length.
private static int getUniqueCharCount(String s) {
int[] counts = new int[26];
for(char c : s.toCharArray()) {
if(counts[c - 'a'] > 0)
return -1;
counts[c - 'a']++;
}
return s.length();
}
public static void main(String[] args) {
List<String> arr = new ArrayList<>(Arrays.asList(new String[]{"un","iq","ue"}));
System.out.println("The maximum length is : " + maxLength(arr));
arr = new ArrayList<>(Arrays.asList(new String[]{"cha","r","act","ers"}));
System.out.println("The maximum length is : " + maxLength(arr));
}
}