二进制字符串中 S[i]、S[j] 和 S[j]、S[k] 的按位"AND"相同的三元组的数量
二进制字符串是一种仅包含二进制字符"0"和"1"的字符串。我们给定一个二进制字符串，必须找到满足条件的三元组，即前两个字符的按位"AND"等于后两个字符的按位"AND"。
数学上:
对于 0 <= i < j < k < 长度(给定字符串):(s[i] & s[j]) == (s[j] & s[k])
如果两位都为真，则按位"AND"为真，否则对于任何一位为假或两位都为假，则返回假。
示例
输入
"01010"
输出
8
解释
对于第 0 个索引处的 0，我们可以有三元组 (0, 1, 0)、(0, 1, 0) (0, 0, 1)、(0, 1, 0) 和 (0, 0, 0)。
对于下一个 1:(1, 0, 1) 和 (1, 0, 0)
对于下一个 0:(0, 1, 0)
方法 1
在此程序中，我们将使用强力方法获取所有三元组，然后检查每个三元组是否符合给定条件。
首先，我们将创建一个函数，该函数将接受给定字符串的单个参数并返回所需的结果。
在函数中，我们将获取字符串的大小，然后使用嵌套的 for 循环遍历字符串并获取所有三元组。
我们将维护一个变量来存储计数，如果任何三元组满足给定条件，则我们将增加计数。
在主函数中，我们将调用该函数并打印结果。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数获取所需的解决方案
int countTriplets(string str){
int len = str.size(); // 获取字符串的大小
int ans = 0; // 变量存储计数
// 使用嵌套的三个 for 循环获取所有三元组
for (int i = 0; i < len; i++){
int a = str[i] -'0'; // current bit
for (int j = i + 1; j < len; j++){
int b = str[j] - '0'; // current bit
for (int k = j + 1; k < len; k++){
int c = str[k] - '0'; // current bit
if((a & b) == (b & c)){
ans++; // 增加计数
}
}
}
}
return ans; // 返回最终计数
}
int main(){
string str = "01010"; // 给定字符串
cout<<"给定字符串中的三元组数量为:" << countTriplets(str) << endl;
return 0;
}
输出
给定字符串中的三元组数量为:8
时间和空间复杂度
上述代码的时间复杂度为 O(N^3)，其中 N 是给定字符串的大小。这里我们在嵌套的 for 循环中遍历字符串三次，使时间复杂度很高。
我们在这里没有使用任何额外的空间，这使得上述代码的空间复杂度为 O(1) 或常数。
方法 2
在此方法中，我们将使用前缀和后缀数组来存储零的数量，以降低时间复杂度。
我们将维护数组并遍历给定的字符串以获取结果。
在遍历中，如果字符串的当前索引为"0"，则我们只需将当前索引号乘以剩余索引的减一即可。
如果当前索引值为"1"，则我们将使用前缀 * 后缀的概念，并将索引减去前缀乘以剩余元素减去后缀，这将为我们提供最终答案。
示例
#include <bits/stdc++.h>
使用命名空间 std;
// 函数来获取所需的解决方案
int countTriplets(string str){
int len = str.size(); // 获取字符串的大小
int ans = 0; // 存储计数的变量
int prefix[len], suffix[len];
// 遍历字符串以获取前缀数组
prefix[0] = str[0] == '0';
for (int i = 1; i < len; ++i) {
prefix[i] = prefix[i-1] + (str[i] == '0');
}
// 遍历字符串以获取后缀数组
suffix[len-1] = str[len-1] == '0';
for (int i = len - 2; i >= 0; --i) {
suffix[i] = suffix[i+1] + (str[i] == '0');
}
// 遍历字符串以获取最终答案
for (int i = 1; i < len - 1; i++) {
if (str[i] == '0') {
ans += i * (len - i - 1);
}
else {
ans += prefix[i - 1] * suffix[i + 1];
ans += (i - prefix[i - 1]) * (len - i - 1 - suffix[i + 1]);
}
}
return ans; // 返回最终计数
}
int main(){
string str = "01010"; // 给定字符串
cout<<"给定字符串中的三元组数量为:"<<countTriplets(str)<<endl;
return 0;
}
输出
给定字符串中的三元组数量为:8
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定字符串的大小。
在上述代码中，我们使用额外的数组来存储零的前缀和后缀计数，使空间复杂度为线性，即 O(N)。
结论
在本教程中，我们实现了一个程序来查找给定二进制字符串中存在的三元组的数量，该三元组符合给定条件:对于 0 <= i < j < k < 长度(给定字符串):(s[i] & s[j]) == (s[j] & s[k])。我们实现了两个程序，一个是使用嵌套 for 循环并使用强力方法查找所有三元组，另一个是通过维护前缀和后缀的总和并通过数学方法查找结果。
