Skip to content

Latest commit

 

History

History
226 lines (178 loc) · 6.46 KB

File metadata and controls

226 lines (178 loc) · 6.46 KB
comments difficulty edit_url rating source tags
true
困难
2221
第 32 场双周赛 Q4
位运算
哈希表
字符串

English Version

题目描述

给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。

「超赞子字符串」需满足满足下述两个条件:

  • 该字符串是 s 的一个非空子字符串
  • 进行任意次数的字符交换后,该字符串可以变成一个回文字符串

 

示例 1:

输入:s = "3242415"
输出:5
解释:"24241" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "24142"

示例 2:

输入:s = "12345678"
输出:1

示例 3:

输入:s = "213123"
输出:6
解释:"213123" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "231132"

示例 4:

输入:s = "00"
输出:2

 

提示:

  • 1 <= s.length <= 10^5
  • s 仅由数字组成

解法

方法一:状态压缩 + 前缀和思想

根据题目描述,“超赞子字符串”中的字符可以通过交换得到回文字符串,因此,“超赞子字符串”中最多有一个数字字符出现奇数次,其余数字字符出现偶数次。

我们可以用一个整数 $st$ 来表示当前前缀字符串中数字字符出现的奇偶性,其中 $st$ 的第 $i$ 位表示数字字符 $i$ 出现的奇偶性,即 $st$ 的第 $i$ 位为 $1$ 表示数字字符 $i$ 出现奇数次,为 $0$ 表示数字字符 $i$ 出现偶数次。

而如果子字符串 $s[j,..i]$ 是“超赞字符串”,那么前缀字符串 $s[0,..i]$ 的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $st'$ 的二进制位中,最多只有一位不同。这是因为,二进制位不同,表示奇偶性不同,而奇偶性不同,就意味着子字符串 $s[j,..i]$ 中该数字出现的次数为奇数次。

所以,我们可以用哈希表或数组记录所有状态 $st$ 第一次出现的位置。若当前前缀字符串的状态 $st$ 在哈希表中已经存在,那么说明当前前缀字符串的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $st'$ 的二进制位中,所有位都相同,即子字符串 $s[j,..i]$ 是“超赞字符串”,更新答案的最大值。或者,我们可以枚举每一位,将当前前缀字符串的状态 $st$ 的第 $i$ 位取反,即 $st \oplus 2^i$,然后判断 $st \oplus 2^i$ 是否在哈希表中,若在,那么说明当前前缀字符串的状态 $st$ 与前缀字符串 $s[0,..j-1]$ 的状态 $st' \oplus 2^i$ 的二进制位中,只有第 $i$ 位不同,即子字符串 $s[j,..i]$ 是“超赞字符串”,更新答案的最大值。

最后,返回答案即可。

时间复杂度 $O(n \times C)$,空间复杂度 $O(2^C)$。其中 $n$$C$ 分别为字符串 $s$ 的长度和数字字符的种类数。

Python3

class Solution:
    def longestAwesome(self, s: str) -> int:
        st = 0
        d = {0: -1}
        ans = 1
        for i, c in enumerate(s):
            v = int(c)
            st ^= 1 << v
            if st in d:
                ans = max(ans, i - d[st])
            else:
                d[st] = i
            for v in range(10):
                if st ^ (1 << v) in d:
                    ans = max(ans, i - d[st ^ (1 << v)])
        return ans

Java

class Solution {
    public int longestAwesome(String s) {
        int[] d = new int[1024];
        int st = 0, ans = 1;
        Arrays.fill(d, -1);
        d[0] = 0;
        for (int i = 1; i <= s.length(); ++i) {
            int v = s.charAt(i - 1) - '0';
            st ^= 1 << v;
            if (d[st] >= 0) {
                ans = Math.max(ans, i - d[st]);
            } else {
                d[st] = i;
            }
            for (v = 0; v < 10; ++v) {
                if (d[st ^ (1 << v)] >= 0) {
                    ans = Math.max(ans, i - d[st ^ (1 << v)]);
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int longestAwesome(string s) {
        vector<int> d(1024, -1);
        d[0] = 0;
        int st = 0, ans = 1;
        for (int i = 1; i <= s.size(); ++i) {
            int v = s[i - 1] - '0';
            st ^= 1 << v;
            if (~d[st]) {
                ans = max(ans, i - d[st]);
            } else {
                d[st] = i;
            }
            for (v = 0; v < 10; ++v) {
                if (~d[st ^ (1 << v)]) {
                    ans = max(ans, i - d[st ^ (1 << v)]);
                }
            }
        }
        return ans;
    }
};

Go

func longestAwesome(s string) int {
	d := [1024]int{}
	d[0] = 1
	st, ans := 0, 1
	for i, c := range s {
		i += 2
		st ^= 1 << (c - '0')
		if d[st] > 0 {
			ans = max(ans, i-d[st])
		} else {
			d[st] = i
		}
		for v := 0; v < 10; v++ {
			if d[st^(1<<v)] > 0 {
				ans = max(ans, i-d[st^(1<<v)])
			}
		}
	}
	return ans
}

TypeScript

function longestAwesome(s: string): number {
    const d: number[] = Array(1024).fill(-1);
    let [st, ans] = [0, 1];
    d[0] = 0;

    for (let i = 1; i <= s.length; ++i) {
        const v = s.charCodeAt(i - 1) - '0'.charCodeAt(0);
        st ^= 1 << v;

        if (d[st] >= 0) {
            ans = Math.max(ans, i - d[st]);
        } else {
            d[st] = i;
        }

        for (let v = 0; v < 10; ++v) {
            if (d[st ^ (1 << v)] >= 0) {
                ans = Math.max(ans, i - d[st ^ (1 << v)]);
            }
        }
    }

    return ans;
}