跳转至

1542. 找出最长的超赞子字符串

来源第 32 场双周赛 Q4难度困难分数2221

题目描述

给你一个字符串 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 仅由数字组成

解法

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

思考

超赞子串重排后能成回文，即最多一个数字出现奇数次。\(n\le 10^5\)，不能枚举子串再统计。数字只有 \(0\)–\(9\)，奇偶可用 \(10\) 位掩码表示。

前缀掩码 \(st\) 记录每种数字的奇偶。子串 \(s[j+1..i]\) 合法，当且仅当 \(st_i\) 与 \(st_j\) 至多一位不同。哈希表记下每种掩码首次出现的位置：相等掩码给出全偶数段，翻转一位后命中则给出恰一个奇数。取最长即可。

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

我们可以用一个整数 \(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\) 的长度和数字字符的种类数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}

评论