1542. Find Longest Awesome Substring

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.

// OJ: https://leetcode.com/problems/find-longest-awesome-substring/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};