C++ 计算具有每个字符的偶数频率和一个异常的子字符串的数量

在这个问题中，我们将计算给定字符串的子字符串数量，其中包含具有偶数频率的所有字符或任何一个具有奇数频率的单个字符。

我们将使用位掩码技术来解决这个问题。在位掩码中，二进制字符串的每个位表示一个字符。

问题陈述 - 给定长度为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 - 将矩阵[0]初始化为1，因为空字符串始终有效。

步骤4 - 开始遍历字符串。

步骤5 - 将1左移字符值的位数，并将其与位掩码进行异或操作。这意味着我们将当前字符添加到掩码中。

步骤6 - 将矩阵列表中与相同bitMask相同的数量添加到’cnt’中。例如，在字符串’acbbe’中，第1个索引和第3个索引的位掩码变为相同。因此，我们可以取出’bb’子字符串。

步骤7 - 使用循环进行0到20次迭代。在每次迭代中，将1左移p位，并将其与位掩码进行异或操作，以从子字符串中删除字符。然后将之前出现过的相同掩码数量添加到’cnt’变量中。

步骤8 - 增加列表中当前位掩码的值。

步骤9 - 返回’cnt’的值。

示例

#include <bits/stdc++.h>
using namespace std;

vector<int> matrix;
long long getSubStrings(string α) {
   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

时间复杂度 – 遍历字符串的时间复杂度为O(N)。

空间复杂度 – 唯一字符的数量为M时，空间复杂度为O(2M)。

程序员可以通过检查每个子串是否符合问题陈述来解决问题。然而，位掩码是解决这类问题的最佳技术。