查找具有给定范围内的最大元素和的 N 长度二进制字符串

---

我们将得到一个数组，该数组将包含表示范围的数对，其值范围为 0（包含）到 N（不包含）。这里，N 是我们必须返回作为答案的二进制字符串的大小。对于所有给定的范围，我们必须最大化零和一的频率乘积之和。我们将实现两种方法，一种是通过查找所有字符串的朴素方法，另一种是高效的解决方案。

示例

输入 1

给定数组：{{1,3}, {2,4}, {2,5}}

字符串长度：6

输出 − 101010（可能还有其他输出，但每个输出都将给出最大结果 8）。

解释 − 对于范围 1 到 3，我们有 1 的频率为 1，0 的频率为 2；对于范围 2 到 4，1 的频率为 2，0 的频率为 1；对于范围 2 到 5，1 和 0 的频率都为 2。这给了我们 (1*2) + (2*1) + (2*2) 的和，即 8，这是最大值。

输入 2

给定数组：{{1,2}}

字符串长度：3

输出 101（最大输出为 1，可以从 001、010、101、110 中得到）。

解释 − 所有可能的字符串是 000、001、010、100、011、101、110、111。可以达到的最大和是 1。

朴素方法

我们已经看到了示例，现在让我们来看主要方法。

在这种方法中，我们将生成所有可能的二进制字符串，并在得到它们之后，检查每个字符串哪个产生最佳的和。我们将使用递归来生成所有字符串，然后对于每个字符串，我们将计算频率乘积的和，然后与最大值进行比较。

示例

#include <iostream>
using namespace std;
int maxSum = 0;
string ansStr = "";
// function to generate all the strings 
void backtracking(string& str, int idx, int arr[][2], int m, int n){
   if(idx == n){
      int curSum = 0;
      for(int i=0;i<m;i++){
         int freqZ = 0, freqO = 0;
         for(int j=arr[i][0]; j <= arr[i][1]; j++){
            if(str[j] == '1'){
               freqO++;
            }
            else{
               freqZ++;
            }
         }
         curSum += freqO*freqZ;
      }
      if(maxSum < curSum){
         maxSum = curSum;
         ansStr = str;
      }
      return;
   }    
   // adding zero at the current index and calling function 
   str.push_back('0');
   backtracking(str,idx+1,arr,m,n);    
   // updating 0 to 1 and calling function 
   str[idx] = '1';
   backtracking(str,idx+1,arr,m,n);    
   str.pop_back(); // poping the last element
}
string findString(int arr[][2], int m, int n){
   // updating the value of maxSum and ansStr 
   ansStr = "";
   maxSum = 0;
   string temp = "";
   // calling to the function 
   backtracking(temp,0,arr,m,n);    
   return ansStr;
}
int main(){
   int arr[][2] = {{1,3}, {2,4}, {2,5}}; // given array 
   int m = 3; // size of array 
   int n = 6; // length of the string     
   // calling the function 
   string str = findString(arr,m,n);    
   cout<<"The string which will produce the maximum result is "<<str<<endl;
   return 0;
}

输出

The string which will produce the maximum result is 000101

时间和空间复杂度

上述代码的时间复杂度非常低效，为 O(2^N*M*N)，其中 N 是字符串的大小，M 是给定数组的大小。

上述代码的空间复杂度为 O(N)，其中 N 是字符串的大小。

高效方法

在之前的方法中，我们创建每个字符串，然后对其进行测试，这需要 O(N) 的空间复杂度和 O(2^N*N) 的时间复杂度，这根本没有效率。为了简化这个过程，我们可以通过观察来思考。

为了获得最大乘积，我们可以考虑减少 1 和 0 的频率之间的绝对差值。为此，将元素放在交替的位置是最好的方法，这将使时间复杂度线性化。让我们看看代码 −

示例

#include <iostream>
using namespace std;
string findString(int n){
   // making the alternative ones and zeros string 
   string ans = "";    
   // adding total of n elements in the string 
   for(int i=0; i<n; i++){
      if(i & 1){
         // if the current index is odd add zero to the string 
         ans += '0';
      }
      else{
         // if the current index is even add one to the string 
         ans += '1';
      }
   }
   return ans;
}
int main(){
   int arr[][2] = {{1,3}, {2,4}, {2,5}}; // given array 
   int m = 3; // size of array 
   int n = 6; // length of the string     
   // calling the function 
   string str = findString(n);    
   cout<<"The string which will produce the maximum result is "<<str<<endl;
   return 0;
}

输出

The string which will produce the maximum result is 101010

时间和空间复杂度

上述代码的时间复杂度为 O(N)，其中 N 是字符串的长度，这是线性时间复杂度。

上述方法的空间复杂度为 O(1)，因为我们在这里没有使用任何额外的空间。

结论

在本教程中，我们实现了两种方法来创建一个字符串，该字符串将为数组提供的给定范围内存在的 1 和 0 的频率产生最大和。我们使用回溯法实现了第一种方法，但这需要指数级的时间复杂度。之后，我们通过观察实现了一种高效的方法。