diff options
author | Jack Sangdahl <[email protected]> | 2025-02-01 22:50:47 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-01 22:50:47 -0700 |
commit | 8a4cccf73263daae2a4c19f2bfa41cf96187ad56 (patch) | |
tree | eedfa5789c7c0e783c73c129228dd584ab5959d0 /find_longest_awesome_substr.c | |
parent | 21d9f8ba7c8e6d1b3adc284878baca1455f48648 (diff) | |
download | leetcode-8a4cccf73263daae2a4c19f2bfa41cf96187ad56.tar.gz leetcode-8a4cccf73263daae2a4c19f2bfa41cf96187ad56.zip |
1542. find longest awesome substring
Diffstat (limited to 'find_longest_awesome_substr.c')
-rw-r--r-- | find_longest_awesome_substr.c | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/find_longest_awesome_substr.c b/find_longest_awesome_substr.c new file mode 100644 index 0000000..6e4462a --- /dev/null +++ b/find_longest_awesome_substr.c @@ -0,0 +1,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 +} |