数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究统计每个字符出现频率为偶数且最多只有一个字符出现频率为奇数的子字符串
在这个问题中，我们将统计给定字符串中包含所有字符出现频率为偶数或仅有一个字符出现频率为奇数的子字符串的数量。
我们将使用位掩码技术来解决这个问题。在位掩码中，二进制字符串的每个位都表示一个字符。
问题陈述
我们给定一个长度为 N 的字符串 alpha。还给定 'a' <= alpha[i] <= 't'。我们需要统计所有字符出现频率为偶数或仅有一个字符出现频率为奇数且其他字符出现频率为偶数的子字符串的数量。
示例
输入
alpha = "pqq";
输出
5
解释 − 有效的子字符串为 pqq、p、q、q 和 qq。
输入
alpha = "mnbn";
输出
5
解释 − 有效的子字符串为 nbn、m、n、b 和 n。
方法 1
此方法使用位掩码来统计包含所有字符出现频率为偶数或仅一个字符出现频率为奇数的子字符串的数量。
逻辑 − 当我们对两个相同的整数进行异或运算时，结果为 0。
因此，我们将遍历字符串，并将每个字符的值与初始位掩码值进行异或运算。如果之前出现过相同的位掩码，我们可以说该子字符串包含所有字符出现频率为偶数，因为掩码的差值为 0。此外，我们将添加和删除每个字符以统计包含单个字符出现频率为奇数的子字符串。
算法
步骤 1 − 初始化大小为 220 的矩阵列表。
步骤 2 − 将 'bitMask' 初始化为 0，表示初始掩码，并将 'cnt' 初始化为 0 以存储有效子字符串的数量。
步骤 3 − 将 matrix[0] 初始化为 1，因为空字符串始终有效。
步骤 4 − 开始遍历字符串。
步骤 5 − 将 1 左移 char 值，并将其与 bitmask 值进行异或运算。这意味着我们将当前字符添加到掩码中。
步骤 6 − 将矩阵列表中相同 bitMask 的数量添加到 'cnt' 中。例如，在字符串 'acbbe' 中，第 1 个和第 3 个索引处的位掩码变为相同。因此，我们可以取子字符串 'bb'。
步骤 7 − 使用循环进行 0 到 20 次迭代。在每次迭代中，将 1 左移 p，并将其与 bitmask 进行异或运算以从子字符串中删除字符。再次将之前出现的相同掩码的数量添加到 'cnt' 变量中。
步骤 8 − 增加列表中当前 bitmask 的值。
步骤 9 − 返回 'cnt' 值。
示例
以下是上述算法的程序 −
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 220
long long matrix[1 << 20];
long long getSubStrings(char *alpha) {
long long bitMask = 0, cnt = 0;
// One possible way for empty mask
matrix[0] = 1;
for (int i = 0; alpha[i]; i++) {
char c = alpha[i];
// Change the bitmask at char - 'a' value
bitMask ^= 1 << (c - 'a');
// Get valid substrings with the same mask
cnt += matrix[bitMask];
// Traverse all the possible masks
for (int p = 0; p < 20; p++) {
// Change mask and add count of valid substrings to cnt
cnt += matrix[bitMask ^ (1 << p)];
}
// Update frequency of mask
matrix[bitMask]++;
}
return cnt;
}
int main() {
char alpha[] = "pqq";
printf("The total number of substrings according to the problem statement is %lld\n", getSubStrings(alpha));
return 0;
}
输出
The total number of substrings according to the problem statement is 5
#include <bits/stdc++.h>
using namespace std;
vector<int> matrix;
long long getSubStrings(string &alpha) {
matrix.resize(1 << 20);
long long bitMask = 0, cnt = 0;
// One possible way for empty mask
matrix[0] = 1;
for (auto c : alpha) {
// Change the bitmask at char - 'a' value
bitMask ^= 1 << (c - 'a');
// Get valid substrings with the same mask
cnt += matrix[bitMask];
// Traverse all the possible masks
for (int p = 0; p < 20; p++) {
// Change mask and add count of valid substrings to cnt
cnt += matrix[bitMask ^ (1 << p)];
}
// Update frequency of mask
matrix[bitMask]++;
}
return cnt;
}
int main() {
string alpha = "pqq";
cout << "The total number of substrings according to the problem statement is " << getSubStrings(alpha);
return 0;
}
输出
The total number of substrings according to the problem statement is 5
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String alpha = "pqq";
System.out.println("The total number of substrings according to the problem statement is " + getSubStrings(alpha));
}
public static long getSubStrings(String alpha) {
long[] matrix = new long[1 << 20];
long bitMask = 0;
long cnt = 0;
// One possible way for empty mask
matrix[0] = 1;
for (char c : alpha.toCharArray()) {
// Change the bitmask at char - 'a' value
bitMask ^= 1 << (c - 'a');
// Get valid substrings with the same mask
cnt += matrix[(int) bitMask];
// Traverse all the possible masks
for (int p = 0; p < 20; p++) {
// Change mask and add count of valid substrings to cnt
cnt += matrix[(int) (bitMask ^ (1 << p))];
}
// Update frequency of mask
matrix[(int) bitMask]++;
}
return cnt;
}
}
输出
The total number of substrings according to the problem statement is 5
def getSubStrings(alpha):
matrix = [0] * (1 << 20)
bitMask = 0
cnt = 0
# One possible way for empty mask
matrix[0] = 1
for c in alpha:
# Change the bitmask at char - 'a' value
bitMask ^= 1 << (ord(c) - ord('a'))
# Get valid substrings with the same mask
cnt += matrix[bitMask]
# Traverse all the possible masks
for p in range(20):
# Change mask and add count of valid substrings to cnt
cnt += matrix[bitMask ^ (1 << p)]
# Update frequency of mask
matrix[bitMask] += 1
return cnt
alpha = "pqq"
print("The total number of substrings according to the problem statement is", getSubStrings(alpha))
输出
The total number of substrings according to the problem statement is 5
时间复杂度 − 遍历字符串的 O(N)。
空间复杂度 − O(2M)，其中 M 是字符串中唯一的字符。
程序员可以通过获取每个子字符串并检查该子字符串是否根据问题陈述有效来解决问题。但是，位掩码是解决此类问题的最佳技术。
185 次浏览
