leetcode

// 2564. Substring XOR Queries
#include "leetcode.h"

/*
 * you are given a binary string 's' and a 2d integer array 'queries' where
 * 'queries[i] = [first_i, second_i]'. for the i'th query, find the shortest
 * substring of 's' whose decimal value 'val' yields 'second_i' when bitwise
 * xor'd with 'first_i'. in other words, 'val ^ first_i == second_i'. the answer
 * to the i'th query is the endpoints of the substring '[left_i, right_i]' or
 * '[-1, -1]' if no such substring exists. if there are multiple answers, choose
 * the one with the minimum 'left_i'. return an array 'ans' where 'ans[i] =
 * [left_i, right_i]' is the answer to the i'th query. a substring is a
 * contiguous non-empty sequence of characters within a string.
 */

struct hash {
  int key;
  struct hash *next;
  UT_hash_handle hh;
};

void resp(struct hash *entry, int idx, struct hash *entries, int **out) {
  int start = idx, end = idx, target = entry->key;
  while (target >>= 1)
    --start;
  do {
    int res = entry - entries;
    out[res][0] = start;
    out[res][1] = end;
  } while ((entry = entry->next));
}

int **substringXorQueries(char *s, int **queries, int queriesSize,
                          int *queriesColSize, int *returnSize,
                          int **returnColumnSizes) {
  int **ans = (int **)malloc(queriesSize * sizeof(int *));
  *returnColumnSizes = (int *)malloc(queriesSize * sizeof(int));
  for (int i = 0; i < queriesSize; ++i) {
    ans[i] = (int *)malloc(2 * sizeof(int));
    (*returnColumnSizes)[i] = 2;
  }
  *returnSize = queriesSize;
  struct hash *table = NULL, *entry;
  struct hash *const entries =
      (struct hash *)malloc(queriesSize * sizeof(struct hash));
  for (int i = 0; i < queriesSize; ++i) {
    int target = queries[i][0] ^ queries[i][1];
    HASH_FIND_INT(table, &target, entry);
    if (!entry) {
      entries[i].key = target;
      entries[i].next = NULL;
      HASH_ADD_INT(table, key, &entries[i]);
    } else {
      entries[i].next = entry->next;
      entry->next = &entries[i];
    }
  }
  int arr[31], cnt = 0;
  for (int i = 0; s[i]; i++) {
    cnt = 30 == cnt ? 30 : cnt + 1;
    for (int j = cnt - 1; j; --j) {
      arr[j] = (arr[j - 1] << 1) + ('1' == s[i]);
      HASH_FIND_INT(table, &arr[j], entry);
      if (entry) {
        resp(entry, i, entries, ans);
        HASH_DEL(table, entry);
      }
    }
    arr[0] = ('1' == s[i]);
    HASH_FIND_INT(table, &arr[0], entry);
    if (entry) {
      resp(entry, i, entries, ans);
      HASH_DEL(table, entry);
    }
  }
  struct hash *tmp;
  HASH_ITER(hh, table, entry, tmp) {
    do {
      ans[entry - entries][0] = -1;
      ans[entry - entries][1] = -1;
    } while ((entry = entry->next));
  }
  HASH_CLEAR(hh, table);
  free(entries);
  return ans;
}

int main() {
  char *s1 = "101101", *s2 = "0101", *s3 = "1";
  int q1i[2][2] = {{0, 5}, {1, 2}}, q2i[1][2] = {{12, 8}}, q3i[1][2] = {{4, 5}};
  struct two_d_arr *q1 =
      two_d_arr_init(ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
  struct two_d_arr *q2 =
      two_d_arr_init(ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
  struct two_d_arr *q3 =
      two_d_arr_init(ARRAY_SIZE(q3i), ARRAY_SIZE(q3i[0]), q3i);
  int rs1, *rcs1,
      **sxq1 = substringXorQueries(s1, q1->arr, q1->row_size, q1->col_size,
                                   &rs1, &rcs1);
  int rs2, *rcs2,
      **sxq2 = substringXorQueries(s2, q2->arr, q2->row_size, q2->col_size,
                                   &rs2, &rcs2);
  int rs3, *rcs3,
      **sxq3 = substringXorQueries(s3, q3->arr, q3->row_size, q3->col_size,
                                   &rs3, &rcs3);
  for (int i = 0; i < rs1; i++) {
    for (int j = 0; j < rcs1[i]; j++)
      printf("%d ", sxq1[i][j]); // expect: [[0,2],[2,3]]
    printf("\n");
  }
  printf("\n");
  for (int i = 0; i < rs2; i++) {
    for (int j = 0; j < rcs2[i]; j++)
      printf("%d ", sxq2[i][j]); // expect: [[-1,-1]]
    printf("\n");
  }
  printf("\n");
  for (int i = 0; i < rs3; i++) {
    for (int j = 0; j < rcs3[i]; j++)
      printf("%d ", sxq1[i][j]); // expect: [[0,0]]
    printf("\n");
  }
  printf("\n");
  for (int i = 0; i < rs1; i++)
    free(sxq1[i]);
  free(sxq1);
  for (int i = 0; i < rs2; i++)
    free(sxq2[i]);
  free(sxq1);
  for (int i = 0; i < rs3; i++)
    free(sxq3[i]);
  free(sxq3);
  free(rcs1);
  free(rcs2);
  free(rcs3);
  two_d_arr_free(q1);
  two_d_arr_free(q2);
  two_d_arr_free(q3);
}