1.4) Is Subsequence or not?

Is Subsequence: Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Sample Input/Output:

Let’s consider a sample input:

s = "abc"
t = "ahbgdc"

Expected Output:

true

Explanation:
For the given input s = "abc" and t = "ahbgdc", the string s is a subsequence of t, as the characters ‘a’, ‘b’, and ‘c’ appear in the same order in both strings.

Time and Space Complexity:

The time complexity of the solution will be O(max(M, N)), where M is the length of string s and N is the length of string t. We iterate through both strings once.

The space complexity will be O(1) as we use constant extra space.

Now, let’s implement the solution in C++:

#include <iostream>
#include <string>

using namespace std;

bool isSubsequence(string s, string t) {
    int i = 0; // Pointer for string s
    int j = 0; // Pointer for string t

    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) {
            ++i; // Move pointer of s
        }
        ++j; // Move pointer of t
    }

    return i == s.size(); // If all characters of s are found in t
}

int main() {
    string s = "abc";
    string t = "ahbgdc";

    bool result = isSubsequence(s, t);

    cout << "Is '" << s << "' a subsequence of '" << t << "': " << (result ? "true" : "false") << endl;

    return 0;
}

In this implementation, we use two pointers i and j to iterate through strings s and t respectively. We compare the characters at the current positions of the pointers. If they match, we move the pointer of s. In any case, we always move the pointer of t. If we reach the end of s (i.e., i equals the size of s), it means all characters of s have been found in t, and we return true.

The main function demonstrates the usage of the isSubsequence function by checking if string s is a subsequence of string t.

The output for the provided test case will be:

Is 'abc' a subsequence of 'ahbgdc': true