Leetcode 1542. Find Longest Awesome Substring

[Woodyiiiiiii]

1542. Find Longest Awesome Substring

1542. Find Longest Awesome Substring

类似题目：
1371. Find the Longest Substring Containing Vowels in Even Counts

根据题目性质，想到奇偶数，我就想到了状态压缩。之后便是前缀和的思想。

要注意可以构造目标状态，int newMask = mask ^ (1 << j)，利用异或符号达成构造。我就卡在了这一点有些久。

class Solution {

    public int longestAwesome(String s) {
        int mask = 0;
        int ans = 1;
        Map<Integer, Integer> evenMap = new HashMap<>();
        Map<Integer, Integer> oddMap = new HashMap<>();
        evenMap.put(0, 0);

        for (int i = 0; i < s.length(); i++) {
            int digit = s.charAt(i) - '0';
            mask ^= (1 << digit);

            if ((i + 1) % 2 == 0) {
                if (evenMap.containsKey(mask)) {
                    ans = Math.max(ans, i + 1 - evenMap.get(mask));
                }
                for (int j = 0; j < 10; j++) {
                    int newMask = mask ^ (1 << j);
                    if (oddMap.containsKey(newMask)) {
                        ans = Math.max(ans, i + 1 - oddMap.get(newMask));
                    }
                }
            } else {
                if (oddMap.containsKey(mask)) {
                    ans = Math.max(ans, i + 1 - oddMap.get(mask));
                }
                for (int j = 0; j < 10; j++) {
                    int newMask = mask ^ (1 << j);
                    if (evenMap.containsKey(newMask)) {
                        ans = Math.max(ans, i + 1 - evenMap.get(newMask));
                    }
                }
            }

            if ((i + 1) % 2 == 0 && !evenMap.containsKey(mask)) {
                evenMap.put(mask, i + 1);
            } else if ((i + 1) % 2 != 0 && !oddMap.containsKey(mask)) {
                oddMap.put(mask, i + 1);
            }
        }

        return ans;
    }
}