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^5sconsists only of digits.
Related Topics: String, Bit Manipulation
Solution 1.
// 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} };
int state = 0, ans = 0;
for (int i = 0; i < s.size(); ++i) {
state ^= 1 << (s[i] - '0');
if (m.count(state)) ans = max(ans, i - m[state]);
for (int j = 0; j < 10; ++j) {
int prev = state ^ (1 << j);
if (m.count(prev)) ans = max(ans, i - m[prev]);
}
if (!m.count(state)) m[state] = i;
}
return ans;
}
};
Since there are only 1024 states, we can also use vector<int> for the map.
// OJ: https://leetcode.com/problems/find-longest-awesome-substring/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestAwesome(string s) {
int state = 0, ans = 0, N = s.size();
vector<int> m(1024, N);
m[0] = -1;
for (int i = 0; i < s.size(); ++i) {
state ^= 1 << (s[i] - '0');
ans = max(ans, i - m[state]);
for (int j = 0; j < 10; ++j) {
ans = max(ans, i - m[state ^ (1 << j)]);
}
m[state] = min(m[state], i);
}
return ans;
}
};
Java
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;
}
}