aboutsummaryrefslogtreecommitdiff
path: root/find_longest_awesome_substr.py
diff options
context:
space:
mode:
Diffstat (limited to 'find_longest_awesome_substr.py')
-rw-r--r--find_longest_awesome_substr.py31
1 files changed, 31 insertions, 0 deletions
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"))