Given two strings A and B, the task is to count the minimum number of operations required to convert the string A to B. In one operation, select a subsequence from string A and convert every character of that subsequence to the smallest character present in it. If it is not possible to transform, then print “-1”.
Examples:
Input: A = “abcab”, B = “aabab”
Output: 2
Explanation:
Operation 1: Replacing characters from indices {2, 1} by the smallest character from those indices(i.e. ‘b’), transforms A to “abbab”.
Operation 2: Replacing characters from indices {1, 0}, by the smallest character from those indices(i.e. ‘a’), transforms A to “aabab”.
Therefore, the count of operations required to convert string A to B is 2.Input: A = “aaa”, B = “aab”
Output: -1
Explanation:
There is no possible way to convert A to B as string A doesn’t contain ‘b’.
Approach: The approach is based on the idea that if any character at index i of string A is less than the character at index i of string B, then it is impossible to change A to B because changing a character to a character smaller than itself is not allowed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum number // of operation void transformString(string str1, string str2) { // Storing data int N = str1.length(); vector< int > convChar[26]; vector< int > str1array[26]; // Initialize both arrays for ( int i = 0; i < 26; i++) { vector< int > v; convChar[i] = v; str1array[i] = v; } // Stores the index of character map< int , char > convertMap; // Filling str1array, convChar // and hashmap convertMap. for ( int i = 0; i < N; i++) { str1array[str1[i] - 'a' ].push_back(i); } for ( int i = 0; i < N; i++) { // Not possible to convert if (str1[i] < str2[i]) { cout << -1 << endl; return ; } else if (str1[i] == str2[i]) continue ; else { convChar[str2[i] - 'a' ].push_back(i); convertMap[i] = str2[i]; } } // Calculate result // Initializing return values int ret = 0; vector<vector< int > > retv; // Iterating the character from // the end for ( int i = 25; i >= 0; i--) { vector< int > v = convChar[i]; if (v.size() == 0) continue ; // Increment the number of // operations ret++; vector< int > v1 = str1array[i]; // Not possible to convert if (v1.size() == 0) { cout << -1 << endl; return ; } // to check whether the final // element has been added // in set S or not. bool isScompleted = false ; for ( int j = 0; j < v1.size(); j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.find(v1[j]) != convertMap.end()) { char a = convertMap[v1[j]]; // Already converted then // then continue if (a > i + 'a' ) continue ; else { v.push_back(v1[j]); isScompleted = true ; retv.push_back(v); break ; } } else { v.push_back(v1[j]); isScompleted = true ; retv.push_back(v); break ; } } // Not possible to convert if (!isScompleted) { cout << -1 << endl; return ; } } // Print the result cout << ret << endl; } // Driver Code int main() { // Given strings string A = "abcab" ; string B = "aabab" ; // Function Call transformString(A, B); return 0; } |
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ // Function to return the minimum number // of operation static void transformString(String str1, String str2) { // Storing data int N = str1.length(); ArrayList< ArrayList<Integer>> convChar = new ArrayList<>(); ArrayList< ArrayList<Integer>> str1array = new ArrayList<>(); // Initialize both arrays for ( int i = 0 ; i < 26 ; i++) { convChar.add( new ArrayList<>()); str1array.add( new ArrayList<>()); } // Stores the index of character Map<Integer, Character> convertMap = new HashMap<>(); // Filling str1array, convChar // and hashmap convertMap. for ( int i = 0 ; i < N; i++) { str1array.get(str1.charAt(i) - 'a' ).add(i); } for ( int i = 0 ; i < N; i++) { // Not possible to convert if (str1.charAt(i) < str2.charAt(i)) { System.out.println(- 1 ); return ; } else if (str1.charAt(i) == str2.charAt(i)) continue ; else { convChar.get(str2.charAt(i) - 'a' ).add(i); convertMap.put(i,str2.charAt(i)); } } // Calculate result // Initializing return values int ret = 0 ; ArrayList< ArrayList<Integer>> retv = new ArrayList<>(); // Iterating the character from // the end for ( int i = 25 ; i >= 0 ; i--) { ArrayList<Integer> v = convChar.get(i); if (v.size() == 0 ) continue ; // Increment the number of // operations ret++; ArrayList<Integer> v1 = str1array.get(i); // Not possible to convert if (v1.size() == 0 ) { System.out.println(- 1 ); return ; } // To check whether the final // element has been added // in set S or not. boolean isScompleted = false ; for ( int j = 0 ; j < v1.size(); j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.containsKey(v1.get(j))) { char a = convertMap.get(v1.get(j)); // Already converted then // then continue if (a > i + 'a' ) continue ; else { v.add(v1.get(j)); isScompleted = true ; retv.add(v); break ; } } else { v.add(v1.get(j)); isScompleted = true ; retv.add(v); break ; } } // Not possible to convert if (!isScompleted) { System.out.println(- 1 ); return ; } } // Print the result System.out.println(ret); } // Driver Code public static void main (String[] args) { // Given strings String A = "abcab" ; String B = "aabab" ; // Function call transformString(A, B); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to return the minimum number # of operation def transformString(str1, str2): # Storing data N = len (str1) convChar = [] str1array = [] # Initialize both arrays for i in range ( 26 ): convChar.append([]) str1array.append([]) # Stores the index of character convertMap = {} # Filling str1array, convChar # and hashmap convertMap. for i in range (N): str1array[ ord (str1[i]) - ord ( 'a' )].append(i) for i in range (N): # Not possible to convert if (str1[i] < str2[i]): print ( - 1 ) return elif (str1[i] = = str2[i]): continue else : convChar[ ord (str2[i]) - ord ( 'a' )].append(i) convertMap[i] = str2[i] # Calculate result # Initializing return values ret = 0 retv = [] # Iterating the character from # the end for i in range ( 25 , - 1 , - 1 ): v = convChar[i] if ( len (v) = = 0 ): continue # Increment the number of # operations ret + = 1 ; v1 = str1array[i] # Not possible to convert if ( len (v1) = = 0 ): print ( - 1 ) return # To check whether the final # element has been added # in set S or not. isScompleted = False for j in range ( len (v1)): # Check if v1[j] is present # in hashmap or not if (v1[j] in convertMap): a = v1[j] # Already converted then # then continue if (a > i + ord ( 'a' )): continue else : v.append(v1[j]) isScompleted = True retv.append(v) break else : v.append(v1[j]) isScompleted = True retv.append(v) break # Not possible to convert if (isScompleted = = False ): print ( - 1 ) return # Print the result print (ret) # Driver Code A = "abcab" B = "aabab" # Function call transformString(A, B) # This code is contributed by dadi madhav |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to return the minimum number // of operation static void transformString( string str1, string str2) { // Storing data int N = str1.Length; List<List< int >> convChar = new List<List< int >>(); List<List< int >> str1array = new List<List< int >>(); // Initialize both arrays for ( int i = 0; i < 26; i++) { convChar.Add( new List< int >()); str1array.Add( new List< int >()); } // Stores the index of character Dictionary< int , char > convertMap = new Dictionary< int , char >(); // Filling str1array, convChar // and hashmap convertMap. for ( int i = 0; i < N; i++) { str1array[str1[i] - 'a' ].Add(i); } for ( int i = 0; i < N; i++) { // Not possible to convert if (str1[i] < str2[i]) { Console.WriteLine(-1); return ; } else if (str1[i] == str2[i]) continue ; else { convChar[str2[i] - 'a' ].Add(i); convertMap[i] = str2[i]; } } // Calculate result // Initializing return values int ret = 0; List<List< int >> retv = new List<List< int >>(); // Iterating the character from // the end for ( int i = 25; i >= 0; i--) { List< int > v = convChar[i]; if (v.Count == 0) continue ; // Increment the number of // operations ret++; List< int > v1 = str1array[i]; // Not possible to convert if (v1.Count == 0) { Console.WriteLine(-1); return ; } // To check whether the final // element has been added // in set S or not. bool isScompleted = false ; for ( int j = 0; j < v1.Count; j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.ContainsKey(v1[j])) { char a = convertMap[v1[j]]; // Already converted then // then continue if (a > i + 'a' ) continue ; else { v.Add(v1[j]); isScompleted = true ; retv.Add(v); break ; } } else { v.Add(v1[j]); isScompleted = true ; retv.Add(v); break ; } } // Not possible to convert if (!isScompleted) { Console.WriteLine(-1); return ; } } // Print the result Console.WriteLine(ret); } // Driver code static void Main() { // Given strings string A = "abcab" ; string B = "aabab" ; // Function call transformString(A, B); } } // This code is contributed by divyesh072019 |
Javascript
<script> // JavaScript program for the above approach // Function to return the minimum number // of operation function transformString(str1, str2) { // Storing data let N = str1.length let convChar = [] let str1array = [] // Initialize both arrays for (let i = 0; i < 26; i++) { convChar.push([]) str1array.push([]) } // Stores the index of character let convertMap = new Map() // Filling str1array, convChar // and hashmap convertMap. for (let i = 0; i < N; i++) { str1array[str1.charCodeAt(i) - 'a' .charCodeAt(0)].push(i) } for (let i = 0; i < N; i++) { // Not possible to convert if (str1.charCodeAt(i) < str2.charCodeAt(i)) { document.write(-1) return } else if (str1[i] == str2[i]) continue else convChar[str2.charCodeAt(i) - 'a' .charCodeAt(0)].push(i) convertMap[i] = str2[i] } // Calculate result // Initializing return values let ret = 0 let retv = [] // Iterating the character from // the end for (let i = 25; i >= 0; i--) { let v = convChar[i] if (v.length == 0) continue // Increment the number of // operations ret += 1; v1 = str1array[i] // Not possible to convert if (v1.length == 0){ document.write(-1) return } // To check whether the final // element has been added // in set S or not. isScompleted = false for (let j = 0; j < v1.length; j++) { // Check if v1[j] is present // in hashmap or not if (convertMap.has(v1[j])){ let a = v1[j] // Already converted then // then continue if (a > i + 'a' .charCodeAt(0)) continue else { v.push(v1[j]) isScompleted = true retv.append(v) break } } else { v.push(v1[j]) isScompleted = true retv.push(v) break } } // Not possible to convert if (isScompleted == false ){ document.write(-1) return } } // Print the result document.write(ret) } // Driver Code let A = "abcab" let B = "aabab" // Function call transformString(A, B) // This code is contributed by shinjanpatra </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!