1542. Find the longest super substring hash + state compression

1542. Find the longest favorite substring

Give you a string  s . Please return  s  The longest of all   Super substring   The length of .

「 Super substring 」 The following two conditions must be met ：

• The string is  s  A non empty substring of
• After any number of character exchanges , This string can become a palindrome string

Example 1：

 Input ：s = "3242415"
 Output ：5
 explain ："24241"  Is the longest super substring , After exchanging the characters , You can get palindromes  "24142"

Example 2：

 Input ：s = "12345678"
 Output ：1

Example 3：

 Input ：s = "213123"
 Output ：6
 explain ："213123"  Is the longest super substring , After exchanging the characters , You can get palindromes  "231132"

Example 4：

 Input ：s = "00"
 Output ：2

Tips ：

• 1 <= s.length <= 10^5
• s  It's just numbers

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/find-longest-awesome-substring
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

  The result of doing the question

success , Thanks to the construction problem of spirit and God , This kind of question gradually has some ideas

Method ： Hash + State compression

One particular thing to note is , Can a palindrome string be formed , There are actually two situations , One is the odd length and the other is the even length

1. The length is even ： The length of each character is even

2. The length is odd ： One character in the middle , The length is odd , Everything else is even

Then we have an important direction ： Pay attention to the parity of strings .

1. The previous string can find the same parity as the current string , Then the two segments are subtracted , Get that every character is even , Subtract to find the even string ;

2. The parity formed by the previous string , It's one bit worse than the current situation , We get the current parity , Reverse one of them , You can find the string with odd length

3. Because we want the string to be as long as possible , So find someone for the first time key after , No subsequent replacement

4. Parity can be computed by bits 1 and 0 To mark , Find parity by prefix

class Solution {
    public int longestAwesome(String s) {
        long v = 0;
        Map<Long,Integer> map = new HashMap<>();// Parity -> Location 
        map.put(v,-1);
        int n = s.length();
        int ans = 0;
        for(int i =0 ; i < n; i++){
            int index = s.charAt(i)-'0';
            v = v ^ ((long)1<<index);
            ans = Math.max(ans,i-map.getOrDefault(v,i));
            for(int j = 0; j < 10; j++){
                long diff = (v ^ ((long)1<<j));
                ans = Math.max(ans,i-map.getOrDefault(diff,i));
            }
            if(!map.containsKey(v)) map.put(v,i);
        }
        return ans;
    }
}