找出最长的超赞子字符串
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
为什么在计算超赞子字符串时,使用位掩码来表示字符出现的奇偶性是有效的?
▷🦆
在更新位掩码时,为什么选择使用异或操作?这种方式有什么特殊的优势吗?
▷🦆
题解中提到如果两个位置的位掩码相同或相差一个二进制位,则这两个位置之间的子字符串可能是超赞子字符串,请问为什么是这样?能否详细解释其中的逻辑?
▷