C++ 计算具有与字符串的第K个字符相同中值的奇数长度子串的数量

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

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

问题陈述 - 给定一个长度为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的matrix列表。

步骤2 - 将’bitMask’初始化为0，表示初始位掩码，并将’cnt’初始化为0以存储有效子字符串的数量。

步骤3 - 初始化matrix[0]为1，因为空字符串始终有效。

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

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

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

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

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

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

例子

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

int validSubStrs(string α, int K) {
   int len = alpha.size();
   int cnt = 0;
   // Get all substrings which should include the Kth character
   for (int p = 0; p < K; p++) {
      for (int q = K - 1; q < len; q++) {
         string temp = alpha.substr(p, q - p + 1);            
         // If the size of the temp string is odd
         if (temp.size() % 2 != 0) {
            // Sort the string in ascending order
            sort(temp.begin(), temp.end());
            // Check median of the string
            if (temp[(temp.size() - 1) / 2] == alpha[K - 1])
               cnt++;
         }
      }
   }
   return cnt;
}
int main() {
   string alpha = "acdb";
   int K = 2;
   cout << "The number of substrings containing the Kth character as the median is " << validSubStrs(alpha, K);
   return 0;
}

输出

The total number of substrings according to the problem statement is 5

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

空间复杂度 – 字符串中唯一字符的个数为M，则空间复杂度为O(2M)。

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