rust 解法, 执行用时: 5 ms, 内存消耗: 2.2 MB, 提交时间: 2024-05-20 09:06:28

impl Solution {
    pub fn longest_awesome(s: String) -> i32 {
        const D: usize = 10;
        let n = s.len() as i32;
        let mut pos = vec![n; 1 << D]; // n 表示没有找到异或前缀和
        pos[0] = -1; // pre[-1] = 0
        let mut ans = 0;
        let mut pre = 0;
        for (i, c) in s.bytes().enumerate() {
            let i = i as i32;
            pre ^= 1 << (c - b'0');
            for d in 0..D {
                ans = ans.max(i - pos[pre ^ (1 << d)]); // 奇数
            }
            ans = ans.max(i - pos[pre]); // 偶数
            if pos[pre] == n { // 首次遇到值为 pre 的前缀异或和，记录其下标 i
                pos[pre] = i;
            }
        }
        ans
    }
}

javascript 解法, 执行用时: 63 ms, 内存消耗: 51.5 MB, 提交时间: 2024-05-20 09:06:14

/**
 * @param {string} s
 * @return {number}
 */
var longestAwesome = function(s) {
    const D = 10; // s 中的字符种类数
    const n = s.length;
    const pos = Array(1 << D).fill(n); // n 表示没有找到异或前缀和
    pos[0] = -1; // pre[-1] = 0
    let ans = 0;
    let pre = 0;
    for (let i = 0; i < n; i++) {
        pre ^= 1 << (s.charCodeAt(i) - '0'.charCodeAt(0));
        for (let d = 0; d < D; d++) {
            ans = Math.max(ans, i - pos[pre ^ (1 << d)]); // 奇数
        }
        ans = Math.max(ans, i - pos[pre]); // 偶数
        if (pos[pre] === n) { // 首次遇到值为 pre 的前缀异或和，记录其下标 i
            pos[pre] = i;
        }
    }
    return ans;
};

golang 解法, 执行用时: 7 ms, 内存消耗: 4 MB, 提交时间: 2024-05-20 09:06:02

func longestAwesome(s string) (ans int) {
    const D = 10 // s 中的字符种类数
    n := len(s)
    pos := [1 << D]int{}
    for i := range pos {
        pos[i] = n // n 表示没有找到异或前缀和
    }
    pos[0] = -1 // pre[-1] = 0
    pre := 0
    for i, c := range s {
        pre ^= 1 << (c - '0')
        for d := 0; d < D; d++ {
            ans = max(ans, i-pos[pre^(1<<d)]) // 奇数
        }
        ans = max(ans, i-pos[pre]) // 偶数
        if pos[pre] == n { // 首次遇到值为 pre 的前缀异或和，记录其下标 i
            pos[pre] = i
        }
    }
    return
}

cpp 解法, 执行用时: 21 ms, 内存消耗: 11 MB, 提交时间: 2024-05-20 09:05:48

class Solution {
    const int D = 10; // s 中的字符种类数
public:
    int longestAwesome(string s) {
        int n = s.size();
        vector<int> pos(1 << D, n); // n 表示没有找到异或前缀和
        pos[0] = -1; // pre[-1] = 0
        int ans = 0, pre = 0;
        for (int i = 0; i < n; i++) {
            pre ^= 1 << (s[i] - '0');
            for (int d = 0; d < D; d++) {
                ans = max(ans, i - pos[pre ^ (1 << d)]); // 奇数
            }
            ans = max(ans, i - pos[pre]); // 偶数
            if (pos[pre] == n) { // 首次遇到值为 pre 的前缀异或和，记录其下标 i
                pos[pre] = i;
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 1376 ms, 内存消耗: 16.6 MB, 提交时间: 2023-06-08 09:46:35

class Solution:
    def longestAwesome(self, s: str) -> int:
        # 回文字符串的条件
        # 1)每个字符均有偶数个
        # 2)仅存在一个字符为奇数个
        # 字符个数奇偶性压缩
        # 记录当前状态下的最小索引值
        hashmap = {0:-1}
        n = len(s)
        ans = 1
        # 初始状态
        init = 0
        for i in range(n):
            init ^= 1 << int(s[i])
            # 判断全为偶数个
            if init in hashmap:
                ans = max(ans,i - hashmap[init])
            else:
                hashmap[init] = i
            # 枚举所有仅存在一个字符为奇数个的状态
            for j in range(10):
                if init ^ (1 << j) in hashmap:
                    ans = max(ans,i - hashmap[init ^ (1 << j)])
        return ans

python3 解法, 执行用时: 1180 ms, 内存消耗: 16.4 MB, 提交时间: 2023-06-08 09:45:43

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        prefix = {0: -1}
        ans, sequence = 0, 0

        for j in range(n):
            digit = ord(s[j]) - ord("0")
            sequence ^= (1 << digit)
            if sequence in prefix:
                ans = max(ans, j - prefix[sequence])
            else:
                prefix[sequence] = j
            for k in range(10):
                if sequence ^ (1 << k) in prefix:
                    ans = max(ans, j - prefix[sequence ^ (1 << k)])
        
        return ans

java 解法, 执行用时: 10 ms, 内存消耗: 42.6 MB, 提交时间: 2023-06-08 09:43:04

/**
 * 状态压缩
 **/
class Solution {
    static int[] pre = new int[1 << 11];
    public int longestAwesome(String s) {
        int n = s.length(), status = 0, res = 0;
        Arrays.fill(pre, -2);  // pre数组初始化为-2，代表都没有出现过
        pre[status] = -1;  // 最初的状态为0，代表都出现了0次（偶数次）
        for (int i = 0; i < n; i++) {
            status ^= 1 << (s.charAt(i) - '0');  // 更新当前状态
            if (pre[status] != -2) {  // 之前已经存在过
                res = Math.max(res, i - pre[status]);
            } else {  // 没有存在过
                pre[status] = i;
            }
            for (int j = 0; j < 10; j++) {  // 枚举0-9
                int status1 = status ^ (1 << j);  // 将对应位置的奇偶性改变
                if (pre[status1] != -2) {  // 之前是否出现过
                    res = Math.max(res, i - pre[status1]);
                }
            }
        }
        return res;
    }
}

java 解法, 执行用时: 100 ms, 内存消耗: 43 MB, 提交时间: 2023-06-08 09:42:13

/**
 * 前缀和+状态压缩
 * 
 **/
class Solution {
    public int longestAwesome(String s) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int cur=0;  //状态
        int ans=1;  //记录答案
        map.put(cur,-1); 
        for(int c=0;c<s.length();c++){
            int ch=s.charAt(c)-'0';
            //计数
            cur=cur^(1<<ch);
            //一个数字出现奇数次，其余出现偶数次
            for(int i=0;i<10;i++){
                int next=cur^(1<<i);
                if(map.containsKey(next)){
                    ans=Math.max(ans,c-map.get(next));
                }
            }
            //所有都出现了偶数次
            if(!map.containsKey(cur)){
                map.put(cur,c);
            }else{
                ans=Math.max(ans,c-map.get(cur));
            }
        }
        return ans;
    }
}