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
}
|