


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. p>
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!

php将16进制字符串转为数字的方法:1、使用hexdec()函数,语法“hexdec(十六进制字符串)”;2、使用base_convert()函数,语法“bindec(十六进制字符串, 16, 10)”。

PHP 是一门功能强大的编程语言,广泛应用于 Web 开发领域。其中一个非常常见的情况是需要将字符串转换为小数。这在进行数据处理的时候非常有用。在本文中,我们将介绍如何在 PHP 中将字符串转换为小数。

检测变量是否为字符串的方法:1、利用“%T”格式化标识,语法“fmt.Printf("variable count=%v is of type %T \n", count, count)”;2、利用reflect.TypeOf(),语法“reflect.TypeOf(变量)”;3、利用reflect.ValueOf().Kind()检测;4、使用类型断言,可以对类型进行分组。

删除方法:1、使用TrimSpace()函数去除字符串左右两边的空格,语法“strings.TrimSpace(str)”;2、使用Trim()函数去除字符串左右两边的空格,语法“strings.Trim(str, " ")”;3、使用Replace()函数去除字符串的全部空格,语法“strings.Replace(str, " ", "", -1)”。

转换方法:1、在转换变量前加上用括号括起来的目标类型“(bool)”或“(boolean)”;2、用boolval()函数,语法“boolval(字符串)”;3、用settype()函数,语法“settype(变量,"boolean")”。

在开发PHP应用程序时,有时我们需要去掉字符串前面的某些特定字符或者字符串。在这种情况下,我们需要使用一些PHP函数来实现这一目标。本文将介绍一些PHP函数,帮助您轻松地去掉字符串前面的字符或字符串。

php字符串长度不一致的解决办法:1、通过mb_detect_encoding()函数查看字符串的编码方式;2、通过mb_strlen函数查看具体字符长度;3、使用正则表达式“preg_match_all('/[\x{4e00}-\x{9fff}]+/u', $str1, $matches);”剔除非中文字符即可。

php字符串部分乱码的解决办法:1、使用“mb_substr(strip_tags($str),0,-1,'UTF-8');”截取字符串;2、使用“iconv("UTF-8","GB2312//IGNORE",$data)”转换字符集即可。


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Dreamweaver Mac version
Visual web development tools