Maximize the given function by selecting equal length substrings from the given binary string

Given two binary strings str1 and str2 of the same length, we have to maximize the given function by selecting substrings from the given strings of the same length value. The given function is like this -

fun(str1, str2) = (len(substring))/(2^xor(sub1, sub2)).

Here, len(substring) is the length of the first substring, and xor(sub1, sub2) is the XOR of the given substring, which is possible since they are binary strings.

Example

Input1: string str1 = 10110 & string str2 = 11101 

Output: 3

illustrate

We could choose many different sets of strings to find the solution, but choosing "101" from both strings will XOR zero, which will cause the function to return the maximum value.

Input2: string str1 = 11111, string str2 = 10001 

Output: 1 

illustrate

We can select "1" as substring which will result in this output and if we select any other string it will result in lower value.

Naive method

In this method, we will find all substrings and then compare them to find the solution, but this solution is not efficient and will take a lot of time and space complexity.

The average time complexity of generating substrings of length x is N^2, and then comparing each substring will cost N^2 more. Additionally, we also have to find the XOR of the given substring, which also costs an additional factor of N, which means N^5 will be the time complexity of the above code, which is very inefficient.

Efficient method

idea

The idea here comes from the simple observation that as the XOR value gets higher, it always reduces the answer. Therefore, in order to maximize the function return value, we must reduce the XOR value as much as possible.

In the case where both substrings are zero, the minimum XOR value that can be achieved is zero. Therefore, this problem is actually derived from the longest common substring problem.

When the XOR is zero, the dividend part is 1, so the final answer will be the length of the largest common substring.

Implementation

We have seen the idea to solve the problem, let’s look at the steps to implement the code -

• We will create a function that will accept two given strings as input and return an integer value, which will be our final result.

• In the function, we first get the length of the string and then create a 2D vector of the size multiplied by the given string.

• We will use nested for loops to iterate through the string and get the largest common substring.

• On each iteration we will check if the current indices of the two strings match, then we will get the value from the vector of the last index of the two strings.

• Otherwise, we just set the current index of the vector to zero.

• Additionally, we will maintain a variable to maintain a count of the maximum length of the common substring.

• Finally, we will return the answer and print it in the main function.

Example

#include <bits/stdc++.h>
using namespace std;
// function to get the result
int result(string str1, string str2){
   int n = str1.length(); // size of the first string
   int m = str2.length(); // size of the second string   
   
   // creating vector to store the dynamic programming results 
   vector<vector<int>>dp(n+1, vector<int>(m+1)); 
   int ans = 0; // variable to store the result 
   
   // traversing over the strings using nested for loops 
   for (int i = 1; i <= n; i++){
      for (int j = 1; j <= m; j++){ 
      
         // if current elements of both the string are equal 
         if (str1[i - 1] == str2[j - 1]){
            // getting one maximum of the last two 
            dp[i][j] = 1 + dp[i - 1][j - 1];
            ans = max(ans, dp[i][j]);
         }
      }
   }
   return ans; // return the final answer or count 
} 
int main(){
   string str1 = "10110";
   string str2 = "11101"; 
   
   // calling the function
   cout<<"The maximum score for a given function by selecting equal length substrings from given binary strings is "<< result(str1,str2)<<endl;
   return 0;
}

Output

The maximum score for a given function by selecting equal length substrings from given binary strings is 3

Time and space complexity

The time complexity of the above code is O(N^2) because we use nested for loops and iterate N times each time.

Since we use a two-dimensional array to store elements, the space complexity of the above code is O(N^2).

in conclusion

In this tutorial, we code to implement the maximum score of a given function by selecting substrings of equal length from a given binary string. We've already discussed this naive approach, which is extremely inefficient. Depending on the given function, the value of the XOR is smaller, so we make the XOR zero by getting the longest common substring in O(N^2) time complexity.

The above is the detailed content of Maximize the given function by selecting equal length substrings from the given binary string. For more information, please follow other related articles on the PHP Chinese website!