Convert given string to another by minimum replacements of subsequences by its smallest character

0 0 7 minutes read

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>

Output

Time Complexity: O(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 zambiatek!