Can somebody please help me out with this problem?

what is the minimum number of slices required to make string A equal to string b?

Example:

String A = "gamergirls"
String B = "merils"

ga | mer | g | i | r | ls -> 5 slices to make merils.

Constraints :

• characters in both the strings are lowercase.
• A.length && B.length <= 10^5

CodePudding user response：

• As mentioned by you in the comments for the constraints, I am proposing a O(^AnC_Bn) solution where An is the length of the string A and Bn is the length of the string B.

• Space complexity would be O(An) where An is the length of the string A.

Algorithm:

• We first make simple checks with lengths of A and B. If B is longer, then return -1. If both have same lengths, if they are same, return 0, else -1.

• For A.length() > B.length(),

  • We check for every possible subsequence with length of A with length of B number of 1's in it. For your example, the bits array as in my below code would initially look like,

    0 0 0 0 1 1 1 1 1 1
    

  • This bits array basically means we are going to check for every possible permutation of it including the above one to see if any subsequence of A matches this. The 1 bit should match with corresponding character in B, else it is a failed permutation.

  • If any permutation of bits matches, we count the no. of cuts required to make it a success. For your example, the permutation of bits array would look like below,

    0 0 1 1 1 0 1 0 1 1
    -------------------
    g a m e r g i r l s
    

  • As you can see above, we have 6 segments of 0s and 1s. In the end, we just take minimum of all of the possibilities and return it.

Main Code:

int min_cuts = Integer.MAX_VALUE;
do{
    int ptr = 0;
    for(int i=0;i<bits.length && ptr < B.length();  i){
        if(bits[i] == '1'){
            if(A.charAt(i) == B.charAt(ptr)){
                ptr  ;
            }else{
                break;
            }
        }
    }

    if(ptr == B.length()){
        min_cuts = Math.min(min_cuts, getCuts(bits) - 1);
    }
}while(nextPermutation(bits));

Complete Online Demo

CodePudding user response：

I know this problem requires the solution in Java, but I want offer the solution in C .

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int maximumSize=10;
vector<int> visitedStringA(maximumSize, 0);
vector<int> visitedStringB(maximumSize, 0);
vector<int> marked(maximumSize, 0);
void showContentVector(vector<int>& input)
{
    for(int i=0; i<input.size();   i)
    {
        cout<<input[i]<<", ";
    }
    return;
}
void dfs(int indexStringA, string& stringA, int indexStringB, string& stringB, int& quantity)
{
    if(stringA.size()==0)
    {
        return;
    }
    if(stringB.size()==0)
    {
        return;
    }
    if(visitedStringA[indexStringA]==1)
    {
        return;
    }
    if(visitedStringB[indexStringB]==1)
    {
        return;
    }
    visitedStringA[indexStringA]=1;
    if(stringA[indexStringA]==stringB[indexStringB])
    {
        visitedStringB[indexStringB]=1;
        marked[indexStringA]=1;
          indexStringB;
    }
    for(int nextIndexStringA=(indexStringA 1); nextIndexStringA<stringA.size();   nextIndexStringA)
    {
        dfs(nextIndexStringA, stringA, indexStringB, stringB, quantity);
    }
    if(indexStringA==0)
    {
        for(int i=0; i<stringA.size();   i)
        {
            if(marked[i 1]<stringA.size())
            {
                if(marked[i]!=marked[i 1])
                {
                      quantity;
                }
            }
        }
    }
    return;
}
void solve()
{
    string stringA="gamergirls";
    string stringB="merils";
    int inputQuantity=0;
    cout<<"Before, inputQuantity <- "<<inputQuantity<<endl;
    dfs(0, stringA, 0, stringB, inputQuantity);
    cout<<"After, inputQuantity <- "<<inputQuantity<<endl;
    return;
}
int main()
{
    solve();
    return 0;
}

Here is the result:

Before, inputQuantity <- 0
After, inputQuantity <- 5

Explanation.

If the size of the input string stringA is equal to 0, therefore, the recursive function dfs() must terminate the execution:

if(stringA.size()==0)
{
    return;
}

If the size of the input string stringB is equal to 0, therefore, the recursive function dfs() must terminate the execution:

if(stringB.size()==0)
{
    return;
}

If the concrete symbol indexStringA in the string stringA, having the concrete index, is visited, therefore, the recursive function dfs() must terminate the execution:

if(visitedStringA[indexStringA]==1)
{
    return;
}

If the concrete symbol indexStringB in the string stringB, having the concrete index, is visited, therefore, the recursive function dfs() must terminate the execution:

if(visitedStringB[indexStringB]==1)
{
    return;
}

If the symbol, having the index indexStringA and belonging to stringA, is equal to the concrete symbol, having the index indexStringB and belonging to stringB, therefore, the current index indexStringB will be visited visitedStringB[indexStringB]=1;. Also the transition to the next index of stringB, corresponding to the command indexStringB;, will be performed. The fact of correspondence of two symbols of stringA and stringB will be assigned to the paramter marked as marked[indexStringA]=1;:

if(stringA[indexStringA]==stringB[indexStringB])
{
    visitedStringB[indexStringB]=1;
    marked[indexStringA]=1;
      indexStringB;
}

At the rise from the depth of the rescursive tree and at the achieving of the index indexStringA is equal to 0, the two neighboring items marked[i] and marked[i 1] will be considered. If these two items marked[i] and marked[i 1] are equal to 0 and 1 correspondingly or equal to 1 and 0 correspondingly, therefore, the parameter quantity will be increased on 1. The parameter quantity has the sense the minimum number of slices required to make stringA equal to stringB:

if(indexStringA==0)
{
    for(int i=0; i<stringA.size();   i)
    {
        if(marked[i 1]<stringA.size())
        {
            if(marked[i]!=marked[i 1])
            {
                  quantity;
            }
        }
    }
}

If the next commands will be performed:

cout<<"marked <- ";
showContentVector(marked);

Therefore, the output will be:

marked <- 0, 0, 1, 1, 1, 0, 1, 0, 1, 1,