aboutsummaryrefslogtreecommitdiff
path: root/largest_substr_eq_char.c
blob: b13f459669e29068113d1c30de0c8e45c5e1f63a (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
// 1624. Largest Substring Between Two Equal Characters
#include "leetcode.h"

/*
 * given a string 's', return the length of the longest substring between two
 * equal characters excluding the two characters if there is no such substring
 * return -1. a substring is a contiguous sequence of characters within a
 * string.
 */

int maxLengthBetweenEqualCharacters(char *s) {
  int n = strlen(s), max = -1;
  int *pre_alpha = calloc(26, sizeof(int));
  int *suff_alpha = calloc(26, sizeof(int));
  for (int i = 0; i < n; i++)
    if (!pre_alpha[s[i] - 'a'])
      pre_alpha[s[i] - 'a'] = i + 1;
  for (int i = n - 1; i >= 0; i--)
    if (!suff_alpha[s[i] - 'a'])
      suff_alpha[s[i] - 'a'] = i + 1;
  for (int i = 0; i < 26; i++)
    max = fmax(max, suff_alpha[i] - pre_alpha[i] - 1);
  free(pre_alpha), free(suff_alpha);
  return max;
}

int main() {
  char *s1 = "aa", *s2 = "abca", *s3 = "cbzxy";
  printf("%d\n", maxLengthBetweenEqualCharacters(s1)); // expect: 0
  printf("%d\n", maxLengthBetweenEqualCharacters(s2)); // expect: 2
  printf("%d\n", maxLengthBetweenEqualCharacters(s3)); // expect: -1
}