diff options
Diffstat (limited to 'max_len_concat_str.c')
-rw-r--r-- | max_len_concat_str.c | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/max_len_concat_str.c b/max_len_concat_str.c new file mode 100644 index 0000000..ff06957 --- /dev/null +++ b/max_len_concat_str.c @@ -0,0 +1,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)); +} |