Open In App

Minimum number of subsequences required to convert one string to another

Last Updated : 24 Feb, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given two strings A and B consisting of only lowercase letters, the task is to find the minimum number of subsequences required from A to form B.

Examples: 

Input: A = “abbace” B = “acebbaae” 
Output:
Explanation: 
Sub-sequences “ace”, “bba”, “ae” from string A used to form string B

Input: A = “abc” B = “cbacbacba” 
Output:
 

Approach:  

  • Maintain an array for each character of A which will store its indexes in increasing order.
  • Traverse through each element of B and increase the counter whenever there is a need for new subsequence.
  • Maintain a variable minIndex which will show that elements greater than this index can be taken in current subsequence otherwise increase the counter and update the minIndex to -1.

Below is the implementation of the above approach. 

C++




// C++ program to find the Minimum number
// of subsequences required to convert
// one string to another
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the no of subsequences
int minSubsequnces(string A, string B)
{
    vector<int> v[26];
    int minIndex = -1, cnt = 1, j = 0;
    int flag = 0;
 
    for (int i = 0; i < A.length(); i++) {
 
        // Push the values of indexes of each character
        int p = (int)A[i] - 97;
        v[p].push_back(i);
    }
 
    while (j < B.length()) {
        int p = (int)B[j] - 97;
 
        // Find the next index available in the array
        int k = upper_bound(v[p].begin(),
                            v[p].end(), minIndex)
                - v[p].begin();
 
        // If Character is not in string A
        if (v[p].size() == 0) {
            flag = 1;
            break;
        }
 
        // Check if the next index is not equal to the
        // size of array which means there is no index
        // greater than minIndex in the array
        if (k != v[p].size()) {
 
            // Update value of minIndex with this index
            minIndex = v[p][k];
            j = j + 1;
        }
        else {
 
            // Update the value of counter
            // and minIndex for next operation
            cnt = cnt + 1;
            minIndex = -1;
        }
    }
    if (flag == 1) {
        return -1;
    }
    return cnt;
}
 
// Driver Code
int main()
{
    string A1 = "abbace";
    string B1 = "acebbaae";
    cout << minSubsequnces(A1, B1) << endl;
    return 0;
}


Java




// Java program to find the Minimum number
// of subsequences required to convert
// one to another
import java.util.*;
 
class GFG {
 
  // This function finds the upper bound of a value
  // in an array
  static int upper_bound(int[] arr, int value)
  {
    int left = 0;
    int right = arr.length;
 
    // Using the binary search method
    while (left < right) {
      int mid = (left + right) / 2;
      if (arr[mid] <= value) {
        left = mid + 1;
      }
      else {
        right = mid;
      }
    }
    return left;
  }
 
  // Function to find the no of subsequences
  static int minSubsequnces(String A, String B)
  {
    int[][] v = new int[26][];
    for (int i = 0; i < v.length; i++) {
      v[i] = new int[0];
    }
    int minIndex = -1;
    int cnt = 1;
    int j = 0;
    int flag = 0;
 
    for (int i = 0; i < A.length(); i++) {
 
      // Push the values of indexes of each character
      int p = (int)A.charAt(i) - 97;
      v[p] = Arrays.copyOf(v[p], v[p].length + 1);
      v[p][v[p].length - 1] = i;
    }
 
    while (j < B.length()) {
      int p = (int)B.charAt(j) - 97;
 
      // Find the next index available in the array
      int k = upper_bound(v[p], minIndex);
 
      // If Character is not in A
      if (v[p].length == 0) {
        flag = 1;
        break;
      }
 
      // Check if the next index is not equal to the
      // size of array which means there is no index
      // greater than minIndex in the array
      if (k != v[p].length) {
 
        // Update value of minIndex with this index
        minIndex = v[p][k];
        j = j + 1;
      }
      else {
 
        // Update the value of counter
        // and minIndex for next operation
        cnt = cnt + 1;
        minIndex = -1;
      }
    }
    if (flag == 1) {
      return -1;
    }
    return cnt;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String A1 = "abbace";
    String B1 = "acebbaae";
    System.out.println(minSubsequnces(A1, B1));
  }
}
 
// This code is contributed by phasing17


Python3




# Python3 program to find the Minimum number
# of subsequences required to convert
# one to another
from bisect import bisect as upper_bound
 
# Function to find the no of subsequences
def minSubsequnces(A, B):
    v = [[] for i in range(26)]
    minIndex = -1
    cnt = 1
    j = 0
    flag = 0
 
    for i in range(len(A)):
 
        # Push the values of indexes of each character
        p = ord(A[i]) - 97
        v[p].append(i)
 
    while (j < len(B)):
        p = ord(B[j]) - 97
 
        # Find the next index available in the array
        k = upper_bound(v[p], minIndex)
 
        # If Character is not in A
        if (len(v[p]) == 0):
            flag = 1
            break
 
        # Check if the next index is not equal to the
        # size of array which means there is no index
        # greater than minIndex in the array
        if (k != len(v[p])):
 
            # Update value of minIndex with this index
            minIndex = v[p][k]
            j = j + 1
        else:
 
            # Update the value of counter
            # and minIndex for next operation
            cnt = cnt + 1
            minIndex = -1
    if (flag == 1):
        return -1
    return cnt
 
# Driver Code
A1 = "abbace"
B1 = "acebbaae"
print(minSubsequnces(A1, B1))
 
# This code is contributed by mohit kumar 29


C#




// C# program to find the Minimum number
// of subsequences required to convert
// one to another
using System;
 
class GFG {
 
  // This function finds the upper bound of a value
  // in an array
  static int upper_bound(int[] arr, int value)
  {
    int left = 0;
    int right = arr.Length;
 
    // Using the binary search method
    while (left < right) {
      int mid = (left + right) / 2;
      if (arr[mid] <= value) {
        left = mid + 1;
      }
      else {
        right = mid;
      }
    }
    return left;
  }
 
  // Function to find the no of subsequences
  static int minSubsequnces(string A, string B)
  {
    int[][] v = new int[26][];
    for (int i = 0; i < v.Length; i++) {
      v[i] = new int[0];
    }
    int minIndex = -1;
    int cnt = 1;
    int j = 0;
    int flag = 0;
 
    for (int i = 0; i < A.Length; i++) {
 
      // Push the values of indexes of each character
      int p = (int)A[i] - 97;
      Array.Resize(ref v[p], v[p].Length + 1);
      v[p][v[p].Length - 1] = i;
    }
 
    while (j < B.Length) {
      int p = (int)B[j] - 97;
 
      // Find the next index available in the array
      int k = upper_bound(v[p], minIndex);
 
      // If Character is not in A
      if (v[p].Length == 0) {
        flag = 1;
        break;
      }
 
      // Check if the next index is not equal to the
      // size of array which means there is no index
      // greater than minIndex in the array
      if (k != v[p].Length) {
 
        // Update value of minIndex with this index
        minIndex = v[p][k];
        j = j + 1;
      }
      else {
 
        // Update the value of counter
        // and minIndex for next operation
        cnt = cnt + 1;
        minIndex = -1;
      }
    }
    if (flag == 1) {
      return -1;
    }
    return cnt;
  }
 
  // Driver Code
  static void Main(string[] args)
  {
    string A1 = "abbace";
    string B1 = "acebbaae";
    Console.WriteLine(minSubsequnces(A1, B1));
  }
}
 
// This code is contributed by phasing17


Javascript




// Javascript program to find the Minimum number
// of subsequences required to convert
// one to another
 
// This function finds the upper bound of a value
// in an array
function upper_bound(arr, value) {
  let left = 0;
  let right = arr.length;
   
  // Using the binary search method
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= value) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}
 
 
// Function to find the no of subsequences
function minSubsequnces(A, B) {
let v = Array.from({length: 26}, () => []);
let minIndex = -1;
let cnt = 1;
let j = 0;
let flag = 0;
 
for (let i = 0; i < A.length; i++) {
 
    // Push the values of indexes of each character
    let p = A.charCodeAt(i) - 97;
    v[p].push(i);
}
 
while (j < B.length) {
    let p = B.charCodeAt(j) - 97;
 
    // Find the next index available in the array
    let k = upper_bound(v[p], minIndex);
 
    // If Character is not in A
    if (v[p].length == 0) {
        flag = 1;
        break;
    }
 
    // Check if the next index is not equal to the
    // size of array which means there is no index
    // greater than minIndex in the array
    if (k != v[p].length) {
 
        // Update value of minIndex with this index
        minIndex = v[p][k];
        j = j + 1;
    } else {
 
        // Update the value of counter
        // and minIndex for next operation
        cnt = cnt + 1;
        minIndex = -1;
    }
}
if (flag == 1) {
    return -1;
}
return cnt;
}
 
// Driver Code
let A1 = "abbace";
let B1 = "acebbaae";
console.log(minSubsequnces(A1, B1));
 
// This code is contributed by phasing17


Output: 

3

 

Time Complexity: O(N1+N2) // N1 is the length of string A and N2 is the length of string B

Auxiliary Space: O(26)



Like Article
Suggest improvement
Previous
Next
Share your thoughts in the comments

Similar Reads