Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1542.html
1542. Find Longest Awesome Substring (Hard)
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 palindrome.
Return the length of the maximum length awesome substring of s
.
Example 1:
Input: s = "3242415" Output: 5 Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.
Example 2:
Input: s = "12345678" Output: 1
Example 3:
Input: s = "213123" Output: 6 Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.
Example 4:
Input: s = "00" Output: 2
Constraints:
1 <= s.length <= 10^5
s
consists only of digits.
Related Topics: String, Bit Manipulation
Solution 1.
-
class Solution { public int longestAwesome(String s) { if (s == null || s.length() == 0) return 0; Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>(); int length = s.length(); int[][] counts = new int[length][10]; int digit0 = s.charAt(0) - '0'; counts[0][digit0] = 1; int num0 = countsToNum(counts[0]); List<Integer> list0 = new ArrayList<Integer>(); list0.add(0); map.put(num0, list0); for (int i = 1; i < length; i++) { int digit = s.charAt(i) - '0'; for (int j = 0; j <= 9; j++) counts[i][j] = counts[i - 1][j]; counts[i][digit] = 1 - counts[i][digit]; int num = countsToNum(counts[i]); List<Integer> list = map.getOrDefault(num, new ArrayList<Integer>()); list.add(i); map.put(num, list); } int maxLength = 1; Set<Integer> visited = new HashSet<Integer>(); for (int i = length - 1; i > 0; i--) { int num = countsToNum(counts[i]); if (num == 0 || (num & (num - 1)) == 0) maxLength = Math.max(maxLength, i + 1); else if (visited.add(num)) { int[] curCounts = new int[10]; System.arraycopy(counts[i], 0, curCounts, 0, 10); List<Integer> list = map.get(num); if (list.size() > 1) maxLength = Math.max(maxLength, i - list.get(0)); for (int j = 0; j <= 9; j++) { curCounts[j] = 1 - curCounts[j]; int newNum = countsToNum(curCounts); if (map.containsKey(newNum)) { List<Integer> newList = map.get(newNum); maxLength = Math.max(maxLength, i - newList.get(0)); } curCounts[j] = 1 - curCounts[j]; } } } return maxLength; } public int countsToNum(int[] counts) { int num = 0; int base = 1; int length = counts.length; for (int i = 0; i < length; i++) { num += counts[i] * base; base *= 2; } return num; } } ############ class Solution { public int longestAwesome(String s) { int[] d = new int[1024]; int st = 0, ans = 1; Arrays.fill(d, -1); d[0] = 0; for (int i = 1; i <= s.length(); ++i) { int v = s.charAt(i - 1) - '0'; st ^= 1 << v; if (d[st] >= 0) { ans = Math.max(ans, i - d[st]); } else { d[st] = i; } for (v = 0; v < 10; ++v) { if (d[st ^ (1 << v)] >= 0) { ans = Math.max(ans, i - d[st ^ (1 << v)]); } } } return ans; } }
-
// OJ: https://leetcode.com/problems/find-longest-awesome-substring/ // Time: O(N) // Space: O(1) since there are at most 2^10=1024 states. class Solution { public: int longestAwesome(string s) { unordered_map<int, int> m{ {0,-1} }; // mask -> index of first occurrence int ans = 0; for (int i = 0, mask = 0; i < s.size(); ++i) { mask ^= 1 << (s[i] - '0'); if (m.count(mask)) ans = max(ans, i - m[mask]); else m[mask] = i; for (int j = 0; j < 10; ++j) { int prev = mask ^ (1 << j); if (m.count(prev)) ans = max(ans, i - m[prev]); } } return ans; } };
-
class Solution: def longestAwesome(self, s: str) -> int: st = 0 d = {0: -1} ans = 1 for i, c in enumerate(s): v = int(c) st ^= 1 << v if st in d: ans = max(ans, i - d[st]) else: d[st] = i for v in range(10): if st ^ (1 << v) in d: ans = max(ans, i - d[st ^ (1 << v)]) return ans
-
func longestAwesome(s string) int { d := [1024]int{} d[0] = 1 st, ans := 0, 1 for i, c := range s { i += 2 st ^= 1 << (c - '0') if d[st] > 0 { ans = max(ans, i-d[st]) } else { d[st] = i } for v := 0; v < 10; v++ { if d[st^(1<<v)] > 0 { ans = max(ans, i-d[st^(1<<v)]) } } } return ans } func max(a, b int) int { if a > b { return a } return b }