Add the minimum subsequence required to append string A to obtain string B

In this problem, we need to construct str2 using the subsequence of str1. To solve this problem, we can find the subsequence of str1 such that it covers the substring with the maximum length of str2. Here we will learn two different ways to solve the problem.

Problem Statement – We are given two strings of different lengths: str1 and str2. We need to construct str2 from str1 according to the following conditions.

• Pick any subsequence from str1 and append it to a new string (initially empty).

We need to return the minimum number of operands required to construct str2, and print -1 if str2 cannot be constructed.

Example

Input– str1 = “acd”, str2 = “adc”

Output– 2

illustrate

• The first subsequence in str1 is "ad". So, our string could be "ad".

• After that, we can get the "c" subsequence from str1 and append it to "ad" to make it "adc".

Input– str1 = "adcb", str2 = "abdca"

Output– 3

illustrate

• The first subsequence is "ab" in str1.

• After that, we can get the "dc" string and the resulting string will be "abdc"

• Next, we can use the "a" subsequence to generate the final string "abdca".

method 1

In this method we will iterate over str1 to find multiple subsequences and append them to the resulting string.

algorithm

• Define the "arr" array of length 26 and initialize all elements to 0 to store the presence of characters in str1.

• Iterate str1 and update the value of the array element according to the ASCII value of the character

• Define the "last" variable and initialize it with -1 to track the last element visited. Additionally, define the "cnt" variable and initialize it to 0 to store the operation count.

• Start using a loop to traverse str2.

• If the current character is not in str1, return -1.

• Initialize the "j" variable using the "last 1" value.

• Use a while loop to iterate until the value of j is less than len, and str1[j] is not equal to the character

• If the value of 'j' is greater than 'len', we traverse 'str1'. Increase the value of the 'cnt' variable, initialize 'last' to -1 because we need to iterate over 'str1' again, decrease the value of 'I' by 1 because we need to consider the current character again, continue using the 'continue' keyword Iterate.

• Update the value of the "last" variable to "j".

• Return "cnt 1" after all iterations of the loop are completed. Here, we need to add "1" to "cnt" because we are not considering the last operation.

Example

#include <iostream>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   int len = str1.length();
   // creating an array of size 26 to store the presence of characters in string str1.
   int arr[26] = {0};
   // storing the presence of characters in string str1.
   for (int i = 0; i < len; i++){
      arr[str1[i] - 'a']++;
   }
   // store the last iterated index of string str1.
   int last = -1;
   //  to store the count of operations.
   int cnt = 0;
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // if the character is not present in string str1, then return -1.
      if (arr[ch - 'a'] == 0){
         return -1;
      }
      // start iterating from the jth index of string str1 to find the character ch.
      int j = last + 1;
      while (j < len && str1[j] != ch){
          j++;
      }
      // if j is equal to the length of string str1, then increment the count, set last to -1, and decrement i.
      if (j >= len){
         cnt++;
         last = -1;
         --i;
         continue;
      }
      // set last to j.
      last = j;
   }
   // return cnt + 1 as we haven't counted the last operation.
   return cnt + 1;
}
int main(){
   string str1 = "acd", str2 = "adc";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Output

Minimum number of operations required to create string B from the subsequences of the string A is: 2

Time complexity – O(N*M), where N is the length of str2 and M is the length of str1.

Space complexity - O(1), since we don't use any dynamic space.

Method 2

In this method, we will use mapping and collection data structures to improve the efficiency of the above method. The logic to solve the problem is the same as above.

algorithm

• Define "chars_mp" to store char -> sets{} as key-value pairs.

• In the mapping, store the index set where specific characters exist in the str1 string

• Define "last" and "cnt" variables

• Start traversing str2. If the size of the collection containing the current character index is zero, -1 is returned.

• Find the upper limit of "last" in the current character index set.

• If the upper limit is not found, increase the value of "cnt" by 1, set "last" to -1, decrease the value of "I" by 1, and use the continue keyword.

• Update the value of the "last" variable.

• After the loop iteration is completed, return the value of the ‘cnt’ variable

Example

#include <iostream>
#include <map> 
#include <set>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   // Length of string str1
   int len = str1.length();
   // creating the map to store the set of indices for each character in str1
   map<char, set<int>> chars_mp;
   // Iterate over the characters of str1 and store the indices of each character in the map
   for (int i = 0; i < len; i++){
      chars_mp[str1[i]].insert(i);
   }
   // store the last visited index of str1
   int last = -1;
   // Stores the required count
   int cnt = 1;
   // Iterate over the characters of str2
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // If the set of indices of str2[i] is empty, then return -1
      if (chars_mp[ch].size() == 0){
         return -1;
      }
      // If the set of indices of str2[i] is not empty, then find the upper bound of last in the set of indices of str2[i]
      // It finds the smallest index of str2[i] which is greater than last
      auto it = chars_mp[ch].upper_bound(last);
      // If the upper bound is equal to the end of the set, then increment the count and update last to -1
       if (it == chars_mp[ch].end()){
          last = -1;
          cnt++;
          // Decrement I by 1 to process the current character again
          --i;
          continue;
      }
      // Update last to the current index
      last = *it;
   }
   return cnt;
}
int main(){
   string str1 = "adcb", str2 = "abdca";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Output

Minimum number of operations required to create string B from the subsequences of the string A is: 3

Time Complexity – O(N*logN), since we iterate over str2 and find the upper bound of the “last” index in the loop.

Space complexity – O(N) because we use a map to store the character index.

The above is the detailed content of Add the minimum subsequence required to append string A to obtain string B. For more information, please follow other related articles on the PHP Chinese website!