C++ 至多只有一个字符出现奇数次的子字符串的数量

子字符串是字符串的连续字符的子集或序列。

现在，在这个问题中，我们需要找出至多只有一个字符出现奇数次的子字符串的数量。让我们看看我们应该如何解决这个问题。

让我们通过一些示例来理解这个问题。

输入 - s = “ksjssjkk”

输出 - 21

解释 - 因为给定字符串中的字符频率如下

• k -> 3

• s -> 3

• j -> 2

现在，至多只有一个字符奇数次出现的子字符串可以是-

• 取每个字符：’k’，’s’，’j’，’s’，’s’，’j’，’k’ = 8

• 每次取2个字母：’ss’，’kk’ = 2

• 每次取3个字母：’sjs’，’jss’，’ssj’，’jkk’ = 4

• 每次取4个字母：’jssj’ = 1

• 每次取5个字母：’sjssj’，’jssjk’，’ssjkk’ = 3

• 每次取6个字母：’jssjkk’ = 1

• 每次取7个字母：’ksjssjk’，’sjssjkk’ = 2

• 每次取8个字母：没有字符串

现在，将子字符串的数量相加，我们得到(8 + 2 + 4 + 1 + 3 + 1 + 2) = 21

输入 – s = “ab”

输出 – 2

解释 – 我们将得到2个子字符串：’a’，’b’

问题说明

让我们试着理解这个问题并找到解决方案。我们必须在字符串中找到那些最多只有一个字母出现奇数次数的子字符串，即，整体上，至多只有一个字母的频率是奇数。

解决方案1：暴力解决方案

方法

这是一种易于理解的方法。我们将简单地运行循环以访问所有子字符串，并将不断检查是否只有一个字母的频率是奇数。如果是的话，我们将把子字符串包含在我们的最终输出中。

示例：C++代码

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

// Function which will check the string is valid
bool checkValid(string s){
   // Define the size of the string
   int n = s.size();
   // Define Frequency vector
   int Freq[26] = {0};
 // Define a variable named oddFreq to calculate total odd frequencies
   int oddFreq = 0;
  // Run a loop to count the frequencies of each character
   for (int i = 0; i < n; i++){
      Freq[s[i] - 'a']++;
   }
    // Run a loop to calculate the number of frequencies that are odd
    for (int i = 0; i < 26; i++){
       if (Freq[i] % 2 != 0)
          oddFreq++;
   }
   // Check if the frequency of any character is odd in number more than one then return false, else return true
   if (oddFreq <= 1) return true;
   else return false;
}
// Function to count the number of substrings with the frequency of at most one character as Odd
int Helper(string s){
   // Define the size of the string
   int n = s.size();
   // Define a variable output initiated by zero
   int output = 0;
   // Run a loop to traverse through the string
   for(int i = 0; i < n; i++){
      // Run another loop inside the first loop to get substrings
      for (int j = i; j < n; j++){
         // Get substring from i to j
         string S = s.substr(i, j - i + 1);
         if (checkValid(S)) output++;
      }
   }
   // Return the final output
   return output;
}
int main(){
   // Give input string by the user
   string s = "ksjssjkk" ;
   // Call the helper function to get the final output
   int output = Helper(s);
   // Print the output
   cout << "The number of substrings with the frequency of at most one character as Odd is: " << output;
      return 0;
}

输出

The number of substrings with the frequency of at most one character as Odd is: 21

上述代码的复杂性

• 时间复杂度 – O(n^3)；其中n是字符串的大小，这里(n^3)是辅助函数的时间复杂度，而checkValid函数本身需要花费O(n)时间执行。

• 空间复杂度 – O(1)；上述代码中没有将任何变量存储在某个数据结构中。

解决方案2：使用位掩码进行优化

位掩码

位掩码是对一个值应用掩码以保留、改变或修改给定信息的行为。掩码确定要采取哪些位和要清除哪些位的二进制数。可以使用各种位操作来使用掩码来表示集合的子集。

解决方法

我们使用位掩码来指示使用奇数次数的字符，并使用哈希表来跟踪以前看到的位掩码。在每次迭代后，我们将hashmap[bitmask]增加一次，表示我们熟悉该位掩码。当output += m[mask]时，将计算出现偶数次的子字符串。而当output += m[mask^ (1<<j)]时，将计算出现奇数次的精确一个字符的子字符串。

示例：C++代码

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

// Function to find the number of substrings with the frequency of at most one character as Odd
int Helper(string s){
   // Declare an Unordered map which would tell us if the frequency of bitmasks is odd or even that is 0 if that character has occurred even times and 1 if it has occurred odd times
   unordered_map<int, int> m;
   // Initiate the frequency bitmask
   m[0] = 1;
   // Store the current bitmask
   int mask = 0;
   // Initialize the output as 0
   int output = 0;
   // Run a loop to start masking
   for (int i = 0; i < s.size(); ++i){
      // masking the current character
      mask ^= (1 << (s[i] - 'a'));
      // Count the substrings that have all alphabets used even the number of times
      output += m[mask];
      for (int j = 0; j < 26; ++j){
         // Count the substrings that have exactly 1 used character
         output += m[mask ^ (1 << j)];
      }
         m[mask]++;
   }
   // Return the final output
   return output;
}
int main(){
   // Give input string by the user
   string s = "ksjssjkk" ;
   // Call the helper function to get the final output
   int output = Helper(s);
   // Print the output
   cout << "The number of substrings with the frequency of at most one character as Odd is: " << output;
      return 0;
}

输出

The number of substrings with the frequency of at most one character as Odd is: 21

上述代码的复杂性

• 时间复杂度- O(n*26),其中n是字符串的大小。对于字符串的每个字符，我们都会检查总共有26个字符。

• 空间复杂度- O(1), 我们只使用了一个map数据结构，它占用了O(26)的空间，与O(1)的空间复杂度相对较小。

结论

在本文中，我们通过使用循环来找到至多包含一个字符的子字符串的频率，首先采用了朴素的方法来获得输出，这是一种容易理解的方法，但唯一的缺点是它会以巨大的时间复杂度执行。然而，我们可以通过使用另一种称为位掩码的技术来轻松推导代码的时间复杂度。这个问题特别是位掩码技术应用的一个奇特的示例，因为它将时间复杂度从O(n^3)减少到O(n)。在本文中，我们学到了位掩码的使用和概念。