aboutsummaryrefslogtreecommitdiff
path: root/find_longest_awesome_substr.c
blob: 6e4462a84cd7d18e274f2697573a597a8eb3e802 (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
// 1542. Find Longest Awesome Substring
#include "leetcode.h"

/*
 * you are given a string 's'. an awesome substring is a non-empty substring of
 * 's' such that we can make any number of swaps in order to make it a
 * palindrome. return the length of the maximum length awesome substring of 's'.
 */

int longestAwesome(char *s) {
  int n = strlen(s), ans = 0, mask = 0, dp[1024];
  memset(dp, n, sizeof(dp));
  dp[0] = -1;
  for (int i = 0; i < n; ++i) {
    mask ^= 1 << (s[i] - '0');
    ans = fmax(ans, i - dp[mask]);
    for (int j = 0; j <= 9; ++j)
      ans = fmax(ans, i - dp[mask ^ (1 << j)]);
    dp[mask] = fmin(dp[mask], i);
  }
  return ans;
}

int main() {
  char *s1 = "3242415", *s2 = "12345678", *s3 = "213123";
  printf("%d\n", longestAwesome(s1)); // expect: 5
  printf("%d\n", longestAwesome(s2)); // expect: 1
  printf("%d\n", longestAwesome(s3)); // expect: 6
}