Count of Subsequences of given string X in between strings Y and Z

Given three strings, ‘X‘, ‘Y‘ and ‘Z‘, the task is to count the number of subsequences of ‘X‘ which is lexiographically greater than or equal to ‘Y‘ and lexiographically lesser than or equal to ‘Z‘.

Examples:

Input: X = “abc”, Y = “a”, Z = “bc”
Output: 6
Explanation: The subsequences of X which are greater than or equal to string ‘Y’ and lesser than or equal to string ‘Z’ are
{ “a”, “b”, “ab”, “ac”, “bc”, “abc” }

Input: X = “ade”, Y = “a”, Z = “dc”
Output: 5
Explanation: The subsequences of X which are greater than or equal to string ‘Y’ and lesser than or equal to string ‘Z’ are
{ “a”, “d”, “ad”, “ae”, “ade”}

Naive Approach: The simplest approach is to generate all subsequences of string ‘X‘ and check if it is greater than or equal to ‘Y‘ and lesser than or equal to ‘Z‘.

Time Complexity: O(2N * N)
Auxiliary Space: O(N)

Efficient Approach: The above approach can also be optimized by using Dynamic Programming because it has overlapping subproblems and optimal substructure. The subproblems can be stored in dp[][][][] table using memoization where dp[idx1][idx2][bound1][bound2] stores the answer from the idx1th position of string ‘X‘ till the end and from the idx2th position of string ‘Y‘ and ‘Z‘ till the end, where bound1 is a boolean variable which tells if the subsequence constructed till idx1 is equal to the corresponding substring of ‘Y‘ till idx2 and bound2 is a boolean variable which tells if the subsequence constructed till idx1 is equal to the corresponding substring of ‘Z‘ till idx2.

Follow the steps below to solve the problem:

  • Initialize a global multidimensional array dp[100][100][2][2] with all values ​​as -1 that stores the result of each recursive call.
  • Define a recursive function, say countOfSubsequence(idx1, idx2, bound1, bound2) by performing the following steps.
    • If the value of idx1 = Xsize,
      • If idx2 = 0then the subsequence is empty, hence return 0.
      • If bound1 is falsethen the subsequence is greater than string ‘Y’, hence return 1.
      • If idx2 < Ysizethe subsequence is equal to string ‘Y’ until idx2 – 1but not completely equal, hence return 0.
    • If the result of the state dp[idx1][idx2][bound1][bound2] is already computed, return this value dp[idx1][idx2][bound1][bound2].
    • In case of the current element being excluded from the subsequence, recursively call the function countOfSubsequence for idx1 + 1.
    • To include the current element at idx1 of string ‘X‘ in the subsequence, we have to check for constraints in both string ‘Y‘ and ‘Z‘,
      • For string ‘Y‘,
        • If bound1 is falsethen the current element can be included as the subsequence is already greater than string ‘Y‘.
        • Else if idx2 >= Ysizethe current element can be included because the subsequence is already equal to string ‘Y‘ and additionally some more characters are being added to it.
        • Else if X[idx1] >= Y[idx2]by including the current element the current subsequence is lexicographically greater than or equal to string ‘Y‘, and hence can be included.
        • If any of the above three conditions are satisfied, then it is possible to include the current element wrt string ‘Y‘.
        • If bound1 is truecheck for X[idx1] == Y[idx2]. If X[idx1] > Y[idx2]update bound1 to false.
      • For string ‘Z‘,
        • If bound2 is falsethen the current element can be included as the subsequence is already lesser than string ‘Z‘.
        • Else if idx2 < Zsize and X[idx1] <= Z[idx2]by including the current element the current subsequence is lexicographically smaller than or equal to string ‘Z‘, and hence can be included.
        • If any of the above two conditions are satisfied, then it is possible to include the current element wrt string ‘Z‘.
        • If bound2 is truecheck for X[idx1] == Z[idx2]. If X[idx1] < Z[idx2]update bound1 to false.
      • After placing the current element at idx1recursively call the countOfSubsequence function (idx1 + 1, idx2 + 1).
  • Print the value returned by the function countOfSubsequence(0, 0, 1, 1) as the result.

Illustration:

X = “ac”

Y = “ab”

Z = “bc”

count(0, 0, 1, 1)

/ (Exclude) Can be included (X[0] == Y[0]X[0] < Z[0])

/ bound1 = 1, bound2 = 0 (as X[0] < Z[0] )

count(1, 0, 1, 1) count(1, 1, 1, 0)

/ (Exclude) Cannot be included / (Exclude) Can be included (X[1] > Y[1]X[1] == Z[1])

/ X[1] > Y[0] / bound1 = 0 (as X[1] > Y[1])

/ but X[1] > Z[0] / bound2 = 0 (as it was previously also 0)

Returns ‘0’ [“”] Returns ‘0’ [“c”] Returns ‘0’ [“a”] Returns ‘1’ [“ac”]

empty subsequence [bound1 = 1,                               [bound1 = 0]

[idx2 == 0] but idx2 < Y.size()]

Hence the final answer is 1ie, “ac”.

Below is the implementation of the above approach:

C++

 

#include <bits/stdc++.h>

using namespace std;

 

int dp[100][100][2][2];

 

string X, Y, Z;

int XSize, YSize, ZSize;

 

int countOfSubsequence(

    int idx1, int idx2,

    bool bound1, bool bound2)

{

 

    

    

    if (idx1 == XSize) {

 

        

        if (idx2 == 0)

            return 0;

 

        

        

        

        

        if (!bound1 or idx2 >= YSize)

            return 1;

 

        

        return 0;

    }

 

    

    

    if (dp[idx1][idx2][bound1][bound2] != -1) {

        return dp[idx1][idx2][bound1][bound2];

    }

 

    

    

    int ans = countOfSubsequence(

        idx1 + 1, idx2,

        bound1, bound2);

 

    

    

    

    

    int isOk = 0;

 

    

    

    

    

    

    

    

    if (!bound1) {

        ++isOk;

    }

 

    

    

    

    

    

    

    

    else if (idx2 >= YSize or X[idx1] >= Y[idx2]) {

        ++isOk;

        bound1 &= (idx2 < YSize

                   and X[idx1] == Y[idx2]);

    }

 

    

    

    

    

    

    

    if (!bound2) {

        ++isOk;

    }

 

    

    

    

    else if (idx2 < ZSize

             and X[idx1] <= Z[idx2]) {

        ++isOk;

        bound2 &= (X[idx1] == Z[idx2]);

    }

 

    

    

    

    

    if (isOk == 2) {

 

        

        ans += countOfSubsequence(

            idx1 + 1, idx2 + 1,

            bound1, bound2);

    }

 

    

    return dp[idx1][idx2][bound1][bound2] = ans;

}

 

int UtilCountOfSubsequence()

{

 

    

    memset(dp, -1, sizeof dp);

 

    

    

    XSize = X.size();

    YSize = Y.size();

    ZSize = Z.size();

 

    

    return countOfSubsequence(0, 0, 1, 1);

}

 

int main()

{

    

    X = "abc";

    Y = "a";

    Z = "bc";

 

    

    

    if (Y > Z) {

        cout << 0 << endl;

        return 0;

    }

 

    cout << UtilCountOfSubsequence()

         << endl;

}

Time Complexity: O(N2 *2*2)
Auxiliary Space: O(N2 *2*2)

Leave a Comment