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
|
// 1239. Maximum Length of a Concatenated String with Unique Characters
#include "leetcode.h"
/*
* given an array of strings 'arr'. a string 's' is formed by the concatenation
* of subsequence of 'arr', that has unique characters. return the maximum
* possible length of 's'. a subsequence is an array that can be derived from
* another array by deleting some or no elements without changing the order of
* the remaining elements.
*/
typedef unsigned char uint8_t;
void dfs(uint8_t **data, uint8_t *len, uint8_t *curr, int pos, int n, int *res,
int size) {
if (pos == n) {
*res = fmax(*res, size);
return;
}
dfs(data, len, curr, pos + 1, n, res, size);
bool pass = true;
for (int i = 0; i < 26; i++) {
curr[i] += data[pos][i];
if (curr[i] > 1)
pass = false;
}
if (pass)
dfs(data, len, curr, pos + 1, n, res, size + len[pos]);
for (int i = 0; i < 26; i++)
curr[i] -= data[pos][i];
}
int maxLength(char **arr, int arr_size) {
uint8_t **data = malloc(arr_size * sizeof(uint8_t *));
uint8_t *len = malloc(arr_size * sizeof(uint8_t));
uint8_t cnt = 0, ans = 0;
for (uint8_t i = 0; i < arr_size; i++)
data[i] = calloc(26, sizeof(uint8_t));
data[cnt] = calloc(26, sizeof(uint8_t));
for (int i = 0; i < arr_size; i++) {
uint8_t l = strlen(arr[i]);
for (int j = 0; j < l; j++) {
data[cnt][arr[i][j] - 'a']++;
if (data[cnt][arr[i][j] - 'a'] > 1) {
memset(data[cnt], 0, 26 * sizeof(uint8_t));
break;
}
if (j == l - 1) {
ans = fmax(ans, l);
len[cnt] = l;
cnt++;
}
}
}
uint8_t *curr = calloc(26, sizeof(uint8_t));
if (cnt > 1)
dfs(data, len, curr, 0, cnt, &ans, 0);
free(curr), free(len);
return ans;
}
int main() {
char a1[3][2] = {"un", "iq", "ue"};
char a2[4][3] = {"cha", "r", "act", "ers"};
char a3[1][26] = {"abcdefghijklmnopqrstuvwxyz"};
printf("%d\n", maxLength(a1, 3));
printf("%d\n", maxLength(a2, 4));
printf("%d\n", maxLength(a3, 1));
}
|