aboutsummaryrefslogtreecommitdiff
path: root/max_len_concat_str.c
blob: ff06957d000860cf83730d6c5e1fda3115f8348a (plain)
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));
}