leetcode
leetcode 1401 ~ 1450
找出最长的超赞子字符串

找出最长的超赞子字符串

难度:

标签:

题目描述

代码结果

运行时间: 165 ms, 内存: 17.4 MB


/*
 * 思路:
 * 1. 使用一个位掩码来表示每个数字的奇偶性。
 * 2. 当两个位置的位掩码相同时,这意味着在它们之间的子字符串满足条件。
 * 3. 使用一个哈希表来记录每个位掩码第一次出现的位置。
 * 4. 遍历字符串并更新哈希表,同时计算最长的满足条件的子字符串长度。
 * 5. 使用Java Stream API来简化部分代码。
 */
import java.util.HashMap;
import java.util.stream.IntStream;

public class Solution {
    public int longestAwesome(String s) {
        HashMap<Integer, Integer> map = new HashMap<>();
        final int[] maxLen = {0};
        final int[] mask = {0};
        map.put(0, -1);
        IntStream.range(0, s.length()).forEach(i -> {
            mask[0] ^= 1 << (s.charAt(i) - '0');
            maxLen[0] = Math.max(maxLen[0], i - map.getOrDefault(mask[0], i));
            map.putIfAbsent(mask[0], i);
            IntStream.range(0, 10).forEach(j -> {
                int newMask = mask[0] ^ (1 << j);
                maxLen[0] = Math.max(maxLen[0], i - map.getOrDefault(newMask, i));
            });
        });
        return maxLen[0];
    }
}

解释

方法:

这个题解的核心思路是使用位掩码来表示字符串s中每个位置上数字字符出现的奇偶性。首先,为每个数字0到9分配一个唯一的二进制位,使用异或操作来更新当前的位掩码。这个位掩码代表了从字符串开始到当前位置的所有字符的奇偶状态。如果两个位置的位掩码相同,或者位掩码相差一个二进制位(即只有一个数字的奇偶性不同),那么这两个位置之间的子字符串是一个超赞子字符串。该方法使用哈希表记录每个位掩码第一次出现的位置,以及该掩码所能达到的最大长度。通过遍历每个可能的掩码,并检查与当前掩码异或后只改变一个位的掩码是否存在,来找到可能的最长超赞子字符串。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在计算超赞子字符串时,使用位掩码来表示字符出现的奇偶性是有效的?
使用位掩码来表示字符的出现奇偶性可以有效地跟踪和更新每个数字字符在字符串中出现的次数是奇数次还是偶数次。每个数字对应一个位,在位掩码中,如果某个位置的位是1,则表示对应的数字出现了奇数次,如果是0,则表示偶数次。这种表示法使得我们能够用一个整数(位掩码)来简洁地表达出所有数字字符的出现奇偶性状态,非常适合进行快速的比较和更新。
🦆
在更新位掩码时,为什么选择使用异或操作?这种方式有什么特殊的优势吗?
异或操作用于更新位掩码时,具有将数字的出现次数从偶数变奇数,或从奇数变偶数的特性。这是因为异或操作对同一个位进行两次相同数值的操作会抵消,即偶数次异或同一个值结果为0(偶数),奇数次结果为该值(奇数)。在本题中,这意味着每次遇到某个数字字符时,通过异或该数字对应的二进制位,可以轻松地更新该数字出现次数的奇偶状态,而无需记录具体的出现次数,从而有效地减少计算和存储需求。
🦆
题解中提到如果两个位置的位掩码相同或相差一个二进制位,则这两个位置之间的子字符串可能是超赞子字符串,请问为什么是这样?能否详细解释其中的逻辑?
如果两个位置的位掩码完全相同,意味着在这两个位置之间的所有字符的出现次数改变都是偶数次(包括零次),因此这段子字符串中每个数字的出现次数都是偶数次。在超赞子字符串的定义中,最多只有一个数字可以出现奇数次,因此,位掩码完全相同符合超赞子字符串的条件。而如果位掩码相差一个二进制位,表示从一个位置到另一个位置的过程中,只有一个数字的出现次数从偶数变为奇数或从奇数变为偶数,这也符合超赞子字符串的特性,即最多只有一个数字出现奇数次。因此,这种位掩码的差异性也能有效地帮助识别可能的超赞子字符串。

相关问题