Given two strings str1 and str2 of lengths N and M respectively, the task is to check if str2 can be formed by appending subsequences of str1 multiple times. If possible, print the minimum number of append operations required. Otherwise, print -1.
Examples:
Input: str1 = “abb”, str2 = “ababbbbb”
Output: 4
Explanation:
String str2 can be formed by appending subsequences of str1 = “ab” + “abb” + “bb” + “b” = “ababbbbb”. Since at least 4 operations are required, print 4.Input: str1 = “mt”, str2 = “atttm”
Output: -1
Explanation:
Since ‘a’ is not present in the string str1, str2 cannot be generated from str1. Therefore, print -1.
Approach: The idea is to use the concept of Hashing based on the following observations below:
- Consider strings str1 = “abb” and str2 = “aba”. Find the position of character str2[0] in str1 whose index is greater than or equals to 0 i.e., index 0 of str1.
- Again, find str2[1] in str1 such that its index is greater than or equals to 1 i.e., index 1 of str1.
- Then, find str2[2] in str1 such that its index is greater than or equals to 2 which does not exist.
- Therefore, start again from index 0 and find str2[2] in str1 having an index greater than or equals to index 0 i.e., index 0 of str1.
- Hence, two subsequences “ab” and “a” can be appended to form “aba”.
Follow the below steps to solve the problem:
- Initialize an array of vectors vec[] of length 26.
- Push all the indices str1 having character ‘a’ in vec[0]. Similarly, push all indices having character ‘b’ in vec[1]. Do this for every character from ‘a’ to ‘z’.
- Initialize a variable result with 1 and position with 0 to store the minimum operations and current position of str1.
- Traverse the string str2 over the range [0, M] and for each character do the following:
- If vec[str2[i] – ‘a’] is empty then the character str2[i] is not present in str1. Hence, the answer is not possible. Therefore, print -1.
- Otherwise, find the lower bound of position in vec[str2[i] – ‘a’]. Let it be p. If p is equals the size of the vec[str2[i] – ‘a’] then increment the result by 1 and decrement i by 1 as answer for character str2[i] is not found yet and set position to 0.
- Otherwise, set position as (vec[p] + 1).
- After traversing, print the result as the minimum operations required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum operations // required to form str2 by adding // subsequences of str1 void find(string str1, string str2) { // Initialize vector of length 26 vector< int > vec1[26]; // Push indices of characters of str1 for ( int i = 0; i < str1.size(); i++) vec1[str1[i] - 'a' ].push_back(i); // Initialize the result & position int result = 1, position = 0; // Traverse the string str2 for ( int i = 0; i < str2.size(); i++) { char c = str2[i]; // Return if no answer exist if (vec1.empty()) { result = -1; break ; } // Pointer of vec1[c-'a'] vector< int >& vec2 = vec1; // Lower bound of position int p = lower_bound(vec2.begin(), vec2.end(), position) - vec2.begin(); // If no index found if (p == vec2.size()) { // Increment result result++; i--; position = 0; continue ; } // Update the position else { position = vec2[p] + 1; } } // Print the result cout << result << '\n' ; } // Driver Code int main() { // Given string str1 & str2 string str1 = "abb" , str2 = "ababbbbb" ; // Function Call find(str1, str2); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { static void find(String str1, String str2) { List<List<Integer> > vec1 = new ArrayList<List<Integer> >(); // Initialize vector of length 26 for ( int i = 0 ; i < 26 ; i++) { vec1.add( new ArrayList<Integer>()); } // Push indices of characters of str1 for ( int i = 0 ; i < str1.length(); i++) vec1.get(str1.charAt(i) - 'a' ).add(i); // Initialize the result & position int result = 1 , position = 0 ; // Traverse the string str2 for ( int i = 0 ; i < str2.length(); i++) { char c = str2.charAt(i); // Return if no answer exist if (vec1.get(c - 'a' ).size() == 0 ) { result = - 1 ; break ; } List<Integer> vec2 = vec1.get(c - 'a' ); // Lower bound of position int p = lower_bound(vec2, position); // If no index found if (p == vec2.size()) { // Increment result result++; i--; position = 0 ; continue ; } // Update the position else { position = vec2.get(p) + 1 ; } } // Print the result System.out.println(result); } // Driver Code static int lower_bound(List<Integer> vec2, int position) { int low = 0 , high = vec2.size() - 1 ; while (low < high) { int mid = (low + high) / 2 ; if (vec2.get(mid) < position) low = mid + 1 ; else high = mid; } return (vec2.get(low) < position) ? low + 1 : low; } public static void main(String[] args) { // Given string str1 & str2 String str1 = "abb" , str2 = "ababbbbb" ; // Function Call find(str1, str2); } } |
Python3
# Python3 program for the above approach from bisect import bisect_left # Function to find minimum operations # required to form str2 by adding # subsequences of str1 def find(str1, str2): # Initialize vector of length 26 vec1 = [[] for i in range ( 26 )] # Push indices of characters of str1 for i in range ( len (str1)): vec1[ ord (str1[i]) - ord ( 'a' )].append(i) # Initialize the result & position result = 1 position = 0 # Traverse the str2 i = 0 while i < len (str2): c = str2[i] # Return if no answer exist if ( len (vec1[ ord (c) - ord ( 'a' )]) = = 0 ): result = - 1 break # Pointer of vec1[c-'a'] vec2 = vec1[ ord (c) - ord ( 'a' )] # Lower bound of position p = bisect_left(vec2, position) #print(c) # If no index found if (p = = len (vec2)): # Increment result result + = 1 #i-=1 position = 0 continue # Update the position else : i + = 1 position = vec2[p] + 1 # Print the result print (result) # Driver Code if __name__ = = '__main__' : # Given str1 & str2 str1 = "abb" str2 = "ababbbbb" # Function Call find(str1, str2) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find minimum operations // required to form str2 by adding // subsequences of str1 static void find( string str1, string str2) { List<List< int >> vec1 = new List<List< int >>(); // Initialize vector of length 26 for ( int i = 0; i < 26; i++) { vec1.Add( new List< int >()); } // Push indices of characters of str1 for ( int i = 0; i < str1.Length; i++) { vec1[str1[i] - 'a' ].Add(i); } // Initialize the result & position int result = 1, position = 0; // Traverse the string str2 for ( int i = 0; i < str2.Length; i++) { char c = str2[i]; // Return if no answer exist if (vec1.Count == 0) { result = -1; break ; } List< int > vec2 = vec1; // Lower bound of position int p = lower_bound(vec2, position); // If no index found if (p == vec2.Count) { // Increment result result++; i--; position = 0; continue ; } // Update the position else { position = vec2[p] + 1; } } // Print the result Console.WriteLine(result); } static int lower_bound(List< int > vec2, int position) { int low = 0, high = vec2.Count - 1; while (low < high) { int mid = (low + high) / 2; if (vec2[mid] < position) { low = mid + 1; } else { high = mid; } } return (vec2[low] < position) ? low + 1 : low; } // Driver Code static public void Main() { // Given string str1 & str2 string str1 = "abb" , str2 = "ababbbbb" ; // Function Call find(str1, str2); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
// JavaScript program for the above approach function find(str1, str2) { // Initialize vector of length 26 const vec1 = new Array(26); for (let i = 0; i < 26; i++) { vec1[i] = []; } // Push indices of characters of str1 for (let i = 0; i < str1.length; i++) { vec1[str1.charCodeAt(i) - 97].push(i); } // Initialize the result & position let result = 1; let position = 0; // Traverse the string str2 for (let i = 0; i < str2.length; i++) { const c = str2.charAt(i); // Return if no answer exist if (vec1.length === 0) { result = -1; break ; } const vec2 = vec1; // Lower bound of position const p = lower_bound(vec2, position); // If no index found if (p === vec2.length) { // Increment result result++; i--; position = 0; continue ; } // Update the position else { position = vec2[p] + 1; } } // Print the result console.log(result); } // Driver Code function main() { // Given string str1 & str2 const str1 = "abb" , str2 = "ababbbbb" ; // Function Call find(str1, str2); } function lower_bound(vec2, position) { let low = 0; let high = vec2.length - 1; while (low < high) { const mid = Math.floor((low + high) / 2); if (vec2[mid] < position) { low = mid + 1; } else { high = mid; } } return (vec2[low] < position) ? low + 1 : low; } main(); // Contributed by adityasha4x71 |
4
Time Complexity: O(N + M log N)
Auxiliary Space: O(M + N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!