Minimum number of subsequences required to convert one string to another
Last Updated :
24 Feb, 2023
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: 3
Explanation:
Sub-sequences “ace”, “bba”, “ae” from string A used to form string B
Input: A = “abc” B = “cbacbacba”
Output: 7
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++
#include <bits/stdc++.h>
using namespace std;
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++) {
int p = (int)A[i] - 97;
v[p].push_back(i);
}
while (j < B.length()) {
int p = (int)B[j] - 97;
int k = upper_bound(v[p].begin(),
v[p].end(), minIndex)
- v[p].begin();
if (v[p].size() == 0) {
flag = 1;
break;
}
if (k != v[p].size()) {
minIndex = v[p][k];
j = j + 1;
}
else {
cnt = cnt + 1;
minIndex = -1;
}
}
if (flag == 1) {
return -1;
}
return cnt;
}
int main()
{
string A1 = "abbace";
string B1 = "acebbaae";
cout << minSubsequnces(A1, B1) << endl;
return 0;
}
|
Java
import java.util.*;
class GFG {
static int upper_bound(int[] arr, int value)
{
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] <= value) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
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++) {
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;
int k = upper_bound(v[p], minIndex);
if (v[p].length == 0) {
flag = 1;
break;
}
if (k != v[p].length) {
minIndex = v[p][k];
j = j + 1;
}
else {
cnt = cnt + 1;
minIndex = -1;
}
}
if (flag == 1) {
return -1;
}
return cnt;
}
public static void main(String[] args)
{
String A1 = "abbace";
String B1 = "acebbaae";
System.out.println(minSubsequnces(A1, B1));
}
}
|
Python3
from bisect import bisect as upper_bound
def minSubsequnces(A, B):
v = [[] for i in range(26)]
minIndex = -1
cnt = 1
j = 0
flag = 0
for i in range(len(A)):
p = ord(A[i]) - 97
v[p].append(i)
while (j < len(B)):
p = ord(B[j]) - 97
k = upper_bound(v[p], minIndex)
if (len(v[p]) == 0):
flag = 1
break
if (k != len(v[p])):
minIndex = v[p][k]
j = j + 1
else:
cnt = cnt + 1
minIndex = -1
if (flag == 1):
return -1
return cnt
A1 = "abbace"
B1 = "acebbaae"
print(minSubsequnces(A1, B1))
|
C#
using System;
class GFG {
static int upper_bound(int[] arr, int value)
{
int left = 0;
int right = arr.Length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] <= value) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
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++) {
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;
int k = upper_bound(v[p], minIndex);
if (v[p].Length == 0) {
flag = 1;
break;
}
if (k != v[p].Length) {
minIndex = v[p][k];
j = j + 1;
}
else {
cnt = cnt + 1;
minIndex = -1;
}
}
if (flag == 1) {
return -1;
}
return cnt;
}
static void Main(string[] args)
{
string A1 = "abbace";
string B1 = "acebbaae";
Console.WriteLine(minSubsequnces(A1, B1));
}
}
|
Javascript
function upper_bound(arr, value) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] <= value) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
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++) {
let p = A.charCodeAt(i) - 97;
v[p].push(i);
}
while (j < B.length) {
let p = B.charCodeAt(j) - 97;
let k = upper_bound(v[p], minIndex);
if (v[p].length == 0) {
flag = 1;
break;
}
if (k != v[p].length) {
minIndex = v[p][k];
j = j + 1;
} else {
cnt = cnt + 1;
minIndex = -1;
}
}
if (flag == 1) {
return -1;
}
return cnt;
}
let A1 = "abbace";
let B1 = "acebbaae";
console.log(minSubsequnces(A1, B1));
|
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
Share your thoughts in the comments
Please Login to comment...