---
# System prepended metadata

title: 1542. Find Longest Awesome Substring
tags: [Leetcode, HashMap, Prefix Sum, Hard]

---

# 1542. Find Longest Awesome Substring
###### tags: `Leetcode` `Hard` `Prefix Sum` `HashMap`
Link: https://leetcode.com/problems/find-longest-awesome-substring/
## 思路
跟这两题很像[1915. Number of Wonderful Substrings](https://hackmd.io/0NLt0f9ZQnicvBhDgaKRIg) [1371. Find the Longest Substring Containing Vowels in Even Counts](https://hackmd.io/vqzHHM8YQhyHFc1m21Ja3g)
用mask记录10个数字出现的次数是奇数还是偶数
用pos记录每个mask出现的最早位置
由于palindrome可以有一个字母出现奇数次 所以跟[1915. Number of Wonderful Substrings](https://hackmd.io/0NLt0f9ZQnicvBhDgaKRIg)很像 把mask里的每一位flip一次 然后更新答案
## Code
```java=
class Solution {
    public int longestAwesome(String s) {
        int[] pos = new int[1024];
        pos[0]=-1;
        for(int i=1; i<pos.length; i++){
            pos[i]=-2;
        }
        int mask = 0;
        int ans = 0;
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            mask ^= 1<<(c-'0');
            if(pos[mask]!=-2) ans = Math.max(ans, i-pos[mask]);
            else pos[mask]=i;
            for(int j=0; j<10; j++){
                if(pos[mask^(1<<j)]!=-2) ans = Math.max(ans, i-pos[mask^(1<<j)]);
            }
        }
        return ans;
    }
}
```