Given two strings S1 and S2, the task is to check if it’s possible to generate string S2 by repeatedly appending subsequences of S1 to the end of an initially empty string. If possible, print “YES” and the minimum number of operations required. Otherwise, print “NO“.
Examples:
Input: S1 = “acebcd”, S2 = “acbcd”
Output:
YES
2
Explanation: Append subsequence “acbc” followed by “d” to obtain S2.Input: S1 = “aceasd”, S2 = “asdxds”
Output: NO
Explanation: Since character ‘x’ is not present in S1, S2 cannot be obtained.
Approach: Follow the steps below to solve the problem:
- Iterate over characters of string S1 and store frequencies of each character in S1 in an array freq[].
- Traverse the string S2 and check if there is any character in S2 which is not present in S1. If any such character is found, print “NO”.
- Otherwise, iterate over characters in S1 and update indices of each character in a Set
- Traverse string S2 and for each character, check if it can be included in the current subsequence of S1 that can be appended.
- If found to be true, set the index of current character as that of the last character appended. Otherwise, increase count of subsequences and set the index of current character as that of the last character appended. Proceed to the next character.
- finally, print “YES” and the count of such subsequences as the required answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include "bits/stdc++.h"using namespace std;// Function for finding minimum// number of operationsint findMinimumOperations(string s, string s1){ // Stores the length of strings int n = s.length(), m = s1.length(); // Stores frequency of // characters in string s int frequency[26] = { 0 }; // Update frequencies of // character in s for (int i = 0; i < n; i++) frequency[s[i] - 'a']++; // Traverse string s1 for (int i = 0; i < m; i++) { // If any character in s1 // is not present in s if (frequency[s1[i] - 'a'] == 0) { return -1; } } // Stores the indices of // each character in s set<int> indices[26]; // Traverse string s for (int i = 0; i < n; i++) { // Store indices of characters indices[s[i] - 'a'].insert(i); } int ans = 1; // Stores index of last // appended character int last = (*indices[s1[0] - 'a'] .begin()); // Traverse string s1 for (int i = 1; i < m; i++) { int ch = s1[i] - 'a'; // Find the index of next // character that can be appended auto it = indices[ch].upper_bound( last); // Check if the current // character be included // in the current subsequence if (it != indices[ch].end()) { last = (*it); } // Otherwise else { // Start a new subsequence ans++; // Update index of last // character appended last = (*indices[ch].begin()); } } return ans;}// Driver Codeint main(){ string S1 = "acebcd", S2 = "acbcde"; int ans = findMinimumOperations( S1, S2); // If S2 cannot be obtained // from subsequences of S1 if (ans == -1) { cout << "NO\n"; } // Otherwise else { cout << "YES\n" << ans; } return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;// Class for finding minimum// number of operationspublic class Main { public static int findMinimumOperations(String s, String s1) { // Stores the length of strings int n = s.length(); int m = s1.length(); // Stores frequency of // characters in string s int[] frequency = new int[26]; // Update frequencies of // character in s for (int i = 0; i < n; i++) { frequency[s.charAt(i) - 'a']++; } // Traverse string s1 for (int i = 0; i < m; i++) { // If any character in s1 // is not present in s if (frequency[s1.charAt(i) - 'a'] == 0) { return -1; } } // Stores the indices of // each character in s List<List<Integer>> indices = new ArrayList<>(); for (int i = 0; i < 26; i++) { indices.add(new ArrayList<Integer>()); } // Traverse string s for (int i = 0; i < n; i++) { // Store indices of characters indices.get(s.charAt(i) - 'a').add(i); } int ans = 2; // Stores index of last // appended character int last = indices.get(s1.charAt(0) - 'a').size() - 1; // Traverse string s1 for (int i = 1; i < m; i++) { int ch = s1.charAt(i) - 'a'; // Find the index of next // character that can be appended int it = binarySearchRight(indices.get(ch), last); // Check if the current // character be included // in the current subsequence if (it != indices.get(ch).size()) { last = it; } // Otherwise else { // Start a new subsequence ans++; // Update index of last // character appended last = indices.get(ch).size(); } } return ans; } // Function to perform binary search // to get the rightmost position of // the element in the given array public static int binarySearchRight(List<Integer> arr, int x) { int left = 0, right = arr.size(); while (left < right) { int mid = (left + right) / 2; if (arr.get(mid) <= x) { left = mid + 1; } else { right = mid; } } return left; } // Driver Code public static void main(String[] args) { String S1 = "acebcd"; String S2 = "acbcde"; int ans = findMinimumOperations(S1, S2); // If S2 cannot be obtained // from subsequences of S1 if (ans == -1) { System.out.println("NO"); } // Otherwise else { System.out.println("YES"); System.out.println(ans); } }}// This code is contributed by phasing17 |
Python3
# Python3 Program to implement# the above approachfrom bisect import bisect ,bisect_left,bisect_right# Function for finding minimum# number of operationsdef findMinimumOperations(s,s1): #Stores the length of strings n = len(s) m = len(s1) # Stores frequency of # characters in string s frequency = [0]*26 # Update frequencies of # character in s for i in range(n): frequency[ord(s[i]) - ord('a')] += 1 # Traverse string s1 for i in range(m): # If any character in s1 # is not present in s if (frequency[ord(s1[i]) - ord('a')] == 0): return -1 # Stores the indices of # each character in s indices = [[] for i in range(26)] # Traverse string s for i in range(n): # Store indices of characters indices[ord(s[i]) - ord('a')].append(i) ans = 2 # Stores index of last # appended character last =len(indices[ord(s1[0])- ord('a')]) - 1 # Traverse string s1 for i in range(1,m): ch = ord(s1[i]) - ord('a') # Find the index of next # character that can be appended it = bisect_right(indices[ch],last) # print(it) # Check if the current # character be included # in the current subsequence if (it != len(indices[ch])): last = it # Otherwise else: # Start a new subsequence ans += 1 # Update index of last # character appended last = len(indices[ch]) return ans# Driver Codeif __name__ == '__main__': S1 = "acebcd" S2 = "acbcde" ans = findMinimumOperations(S1, S2) # If S2 cannot be obtained # from subsequences of S1 if (ans == -1): print("NO") # Otherwise else: print("YES") print(ans)# This code is contributed by mohit kumar 29 |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;class GFG { public static int FindMinimumOperations(string s, string s1) { // Stores the length of strings int n = s.Length; int m = s1.Length; // Stores frequency of // characters in string s int[] frequency = new int[26]; // Update frequencies of // character in s for (int i = 0; i < n; i++) { frequency[s[i] - 'a']++; } // Traverse string s1 for (int i = 0; i < m; i++) { // If any character in s1 // is not present in s if (frequency[s1[i] - 'a'] == 0) { return -1; } } // Stores the indices of // each character in s List<List<int> > indices = new List<List<int> >(); for (int i = 0; i < 26; i++) { indices.Add(new List<int>()); } // Traverse string s for (int i = 0; i < n; i++) { // Store indices of characters indices[s[i] - 'a'].Add(i); } int ans = 2; // Stores index of last // appended character int last = indices[s1[0] - 'a'].Count - 1; // Traverse string s1 for (int i = 1; i < m; i++) { int ch = s1[i] - 'a'; // Find the index of next // character that can be appended int it = BinarySearchRight(indices[ch], last); // Check if the current // character be included // in the current subsequence if (it != indices[ch].Count) { last = it; } // Otherwise else { // Start a new subsequence ans++; // Update index of last // character appended last = indices[ch].Count; } } return ans; } // Function to perform binary search // to get the rightmost position of // the element in the given array public static int BinarySearchRight(List<int> arr, int x) { int left = 0, right = arr.Count; while (left < right) { int mid = (left + right) / 2; if (arr[mid] <= x) { left = mid + 1; } else { right = mid; } } return left; } // Driver Code public static void Main(string[] args) { string S1 = "acebcd"; string S2 = "acbcde"; int ans = FindMinimumOperations(S1, S2); // If S2 cannot be obtained // from subsequences of S1 if (ans == -1) { Console.WriteLine("NO"); } // Otherwise else { Console.WriteLine("YES"); Console.WriteLine(ans); } }}// This code is contributed by phasing17 |
Javascript
// Define function to find minimum operationsfunction findMinimumOperations(s, s1) { // Get length of strings const n = s.length, m = s1.length; // Create frequency array to store frequency of characters in s const frequency = new Array(26).fill(0); // Update frequency of each character in s for (let i = 0; i < n; i++) { frequency[s[i].charCodeAt() - 'a'.charCodeAt()]++; } // Check if all characters in s1 are present in s for (let i = 0; i < m; i++) { if (frequency[s1[i].charCodeAt() - 'a'.charCodeAt()] === 0) { return -1; } } // Create indices array to store indices of each character in s const indices = new Array(26); // Initialize each element of indices array as a Set for (let i = 0; i < 26; i++) { indices[i] = new Set(); } // Update indices array with indices of each character in s for (let i = 0; i < n; i++) { indices[s[i].charCodeAt() - 'a'.charCodeAt()].add(i); } // Initialize variables to keep track of operations let ans = 1; let last = [...indices[s1[0].charCodeAt() - 'a'.charCodeAt()]][0]; // Iterate through each character in s1 for (let i = 1; i < m; i++) { // Get character code of current character in s1 const ch = s1[i].charCodeAt() - 'a'.charCodeAt(); // Get iterator of indices for current character in s const values = indices[ch].values(); // Find first index greater than last let it = values.next(); while (!it.done && it.value <= last) { it = values.next(); } // If all indices are less than or equal to last, increment operations if (it.done) { ans++; last = [...indices[ch]][0]; } else { // Else, update last with the next index last = it.value; } } // Return minimum number of operations required return ans;}// Define two strings S1 and S2const S1 = "acebcd", S2 = "acbcde";// Find minimum number of operations required to convert S1 to S2const ans = findMinimumOperations(S1, S2);// Print "NO" if S1 cannot be converted to S2, else print "YES" followed by the minimum number of operationsif (ans === -1) { console.log("NO");} else { console.log("YES"); console.log(ans);} |
Output:
YES 2
Time Complexity: O(Mlog(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
