Given two strings determine the number of times the first one appears as a subsequence

In this tutorial, we’ll discuss the problem of finding the number of occurrences of a subsequence in a string. First, we’ll define the problem. Then we’ll give an example to explain it. Finally, we’ll present three different approaches to solve this problem.

2. Defining the Problem

We have a string

A subsequence of a string is a sequence that can be derived from the given string by deleting zero or more elements without changing the order of the remaining elements.

Let’s take a look at the following example for a better understanding.

Given a string

Let’s count the number of occurrences of string in string as a subsequence:

As we can see, there are three subsequences of string that are equal to the string . Thus, the answer to the given example is .

3. Recursion Approach

The main idea in this approach is to try every possible subsequence of the string

and see if it matches the string

.

For each character of the string , we’ll have two options. We can leave it so that we don’t consider it in the current subsequence, and we move to the next character. Otherwise, we can take it as a character in our subsequence if it’s equal to the current character of the string .

When we reach the end of the string , we get a subsequence of the string that’s equal to the string . As a result, we increase the count of the subsequences by one. Otherwise, we ignore the current subsequence.

3.1. Algorithm

Let’s take a look at the implementation of the algorithm:

Initially, we declare the

First, since we’re dealing with a recursive function, we’ll set the base conditions to stop searching for answers. We have two situations we have to handle:

1. If we reach the end of and , that means we got a subsequence of that matches the string , so we return to increase the number of subsequences.
2. If we reach the end of the string , that means we didn’t reach the end of . Therefore, we didn’t find a subsequence that matches , and we return .

Second, we have to set the recursive calls. For each character of , we have two options; we can either pick the current character, or leave it:

1. Pick: if the current character of matches the current character of , we try to take it and move both pointers forward.
2. Leave: for each character of , we also have to consider it out of our subsequence. Thus, we try to leave it and move only the pointer of forward.

The sum of these two recursive calls will eventually be the answer to the current state.

Finally, the

3.2. Complexity

The time complexity of this algorithm is

The space complexity of this algorithm is

4. Dynamic Programming Approach

The huge complexity of the previous approach comes from calculating each state

In this approach, we’ll try to memorize the answer of each state

to use it in the future without calculating that state again.

As we see in the previous approach, the answer of state depends on the answers of the state

Finally, the answer to our problem will be stored in the answer of the state

4.1. Algorithm

Let’s take a look at the implementation of the algorithm:

Initially, we declare the

Next, we’ll iterate from the end of the string until the beginning. For each position in the string , we’ll also iterate over the string from the end until the beginning because every state is depending on the states that come after it.

For each state , we’ll check if the current characters of both strings match. If so, we’ll add to the answer of the current state the answer of state , which means we picked the current character of the string . In addition, we add the answer of the state , which means we leave the current character of the string .

Finally, the value of

4.2. Complexity

The complexity of this algorithm is

The space complexity of this algorithm is , which is the size of the memoization array that we use to store the answer of each state.

5. Dynamic Programming Optimization

In this approach, we’ll optimize the space complexity of the previous one. The main idea here will be the same as the previous approach. The only difference is that since each state depends only on the next state

, where

represents any position of the string , we can reduce the first dimension of the memoization array to instead of

(the length of the string ).

For each state, we’ll try to store it in an alternating position of the next state. To do that, we’ll get the advantage of the mod operator. So,

In the end, the answer to our problem will also be stored in the answer of the state .

5.1. Algorithm

Let’s take a look at the implementation of the algorithm:

Initially, we declare the array, which will store the answer of each state . The initial value of the state

Next, we’ll do the same as the previous approach, but instead of putting the original index in the first dimension, we’ll put its module by .

Finally, the value of is equal to the number of subsequences of the string that match the string if we start from the beginning of both strings.

5.2. Complexity

The complexity of this algorithm is , where is the length of the string , and is the length of the string . The reason for this complexity is the same as the previous approach.

The space complexity of this algorithm is

6. Conclusion

In this article, we presented the problem of finding the number of occurrences of a subsequence in a string.

First, we provided an example to explain the problem. Then we explored three different approaches for solving it.

Finally, we walked through their implementations, with each approach having a better space or time complexity than the previous one.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.