The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A Subsequence

A subsequence is a sequence that can be derived from an array or another sequence, by removing zero or more elements, without changing the order of the remaining elements. The subsequence maintains the order it had in the original array or original sequence.

In general, for the original sequence of size n, there can be up to (2ⁿ - 1) non-empty sub-sequences in total.

For example, in the array [1, 2, 3, 4], there are 15 non-empty sub-sequences, which are:

[1], [2], [3], [4], [1,2], [1,3],[1,4], [2,3], [2,4], [3,4], [1,2,3], [1,2,4], [1,3,4], [2,3,4], [1,2,3,4] .

This is the number of combinations, but maintaining the order of appearance in the given (original) array.

A complete (power set) of subsequences of any array includes the empty subsequence: []. With that, the total number of possible subsequences from the original array is 2ⁿ .

Even-number only type subsequences from the 15 subsequences above, are:

[2], [4], [2,4]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Odd-number only type subsequences from the 15 subsequences above, are:

[1], [3], [1,3]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Out of the whole set of possible subsequences, only one or more subsequences with a characteristic description, is usually required.

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable.

The sliding window is a specialized application of the two-pointers technique.

Problem

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 that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

    0 <= s.length <= 100
    0 <= t.length <= 104
    s and t consist only of lowercase English letters.

Note:

The length of t should be at least the length of s.

Best Approach in O(n) Time

The best (efficient) approach is to use a special two-pointers technique. The reader might expect that two-pointers should refer to the same array (string). However, here one pointer refers to one array (string) and the other pointer refers to the other array (string). At the start of the algorithm, the pointer ps points to the first character of s and the pointer pt points to the first character of t.

The algorithm scans the longer string t, one character at a time from its first character. For each of the characters in t, the algorithm checks if the sequence of characters of the shorter string s, are found in the longer string t, in order. This means that the pointer pt, would have to skip some characters in the second string. As soon as s is completely scanned, returned true. If the scanning of t completes while the scanning of s is not complete, return false. It is the first sequence for s encountered in t that matters.

Smart Program in O(n) Time

The smart program using two-pointers is (read through the code and comments):

#include <stdio.h>
#include <stdbool.h>

bool isSubsequence(char s[], char t[], int n1, int n2) {
    //edge case: t cannot be shorter than s
    if (n2 < n1) {
        printf("s cannot be less than t");
        return false;
    }

    int ps = 0, pt = 0;
    //Iterate over t, while comparing with s
    while (pt < n2) {
        if (t[pt] != s[ps])
            pt = pt + 1;    // not found a char match, move to next char in t
        else {   //found a char match
            ps = ps + 1;      // Always move forward in t
            pt = pt + 1;
        }
    }

    if (ps == n1)    //for complete scanning of s
        return true;     //s is subsequence of t
        
    return false;    //otherwise s is not subsequence of t
}

int main(int argc, char **argv) {
    char s1[] = "abc";
    char t1[] = "ahbgdc";
    bool ret1 = isSubsequence(s1, t1, 3, 6);
    if (ret1 == true) printf("%i\n", true); else printf("%i\n", false);
    
    char s2[] = "axc";
    char t2[] = "ahbgdc";
    bool ret2 = isSubsequence(s2, t2, 3, 6);
    if (ret2 == true) printf("%i\n", true); else printf("%i\n", false);
    
    char s3[] = "aec";
    char t3[] = "abcde";
    bool ret3 = isSubsequence(s1, t1, 3, 5);
    if (ret3 == true) printf("%i\n", true); else printf("%i\n", false);
    
    return 0;
}

The output is:

    1    for true
    0    for false
    0    for false

The time complexity is O(n), where n is the length of the longer string. The space complexity is O(n+m), where n is the length of the longer string, and m is the length of the shorter string. The pair of strings (arrays) in the calling function are the same as the pairs of strings (arrays) in the called function. Any extra time or extra space used is ignored, in quoting the time or space complexity.

Note: In order to know the length of a string in C, iterate over the string until '\0' is met. That was not done in the above program in order to save programming text length.

Thanks for reading.