diff options
-rw-r--r-- | find_longest_awesome_substr.c | 29 | ||||
-rw-r--r-- | find_longest_awesome_substr.py | 31 |
2 files changed, 60 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 +} diff --git a/find_longest_awesome_substr.py b/find_longest_awesome_substr.py new file mode 100644 index 0000000..d4113d6 --- /dev/null +++ b/find_longest_awesome_substr.py @@ -0,0 +1,31 @@ +# 1542. Find Longest Awesome Substring + +""" +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'. +""" + + +class Solution(object): + def longestAwesome(self, s): + """ + :type s: str + :rtype: int + """ + ans, mask = 0, 0 + dp = [-1] + [len(s)] * 1023 + for i in range(len(s)): + mask ^= 1 << (ord(s[i]) - 48) + for j in range(11): + check = 1023 & (mask ^ (1 << j)) + ans = max(ans, i - dp[check]) + dp[mask] = min(dp[mask], i) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestAwesome(s="3242415")) + print(obj.longestAwesome(s="12345678")) + print(obj.longestAwesome(s="213123")) |