Algorithms to Check if a String is a Subsequence String of Another String

Given two strings s1 and s2, determine if s1 is a subsequence of s2. A string a is a subsequence of another string b if you can delete some (or 0) characters from b, without changing the order, and get a.

For example, ace is a subsequence of abcde, but eca is not a subsequence of abcde.

Constraints
n ≤ 100,000 where n is the length of s1
m ≤ 100,000 where m is the length of s2

Example 1
Input
s1 = “ppl”
s2 = “apple”

Output
true

Example 2
Input
s1 = “ale”
s2 = “apple”

Output
true

Example 3
Input
s1 = “elppa”
s2 = “apple”

Output
false

Recursive Subsequence String Algorithm

Since we are checking if string s1 is subsequence of s2, if the last character is the same, then we have to check if s1[:-1] (excluding the last character) is the subsequence of s2[:-1]. When s1 is empty, we terminate the recursion and return true.

If the last character mismatches, we can reduce the problem into sub problem: check if string s1 is subsequence of s2[:-1]. And again, if the s2 has a small length than s1, it is impossible for s1 to be sub sequence of s2.

1
2
3
4
5
6
7
8

bool solve(string s1, string s2) {
    if (s1.empty()) return true;
    if (s1.size() > s2.size()) return false;
    if (s1.back() == s2.back()) {
        return solve(s1.substr(0, s1.size() - 1), s2.substr(0, s2.size() - 1));
    }
    return solve(s1, s2.substr(0, s2.size() - 1));
}

bool solve(string s1, string s2) {
    if (s1.empty()) return true;
    if (s1.size() > s2.size()) return false;
    if (s1.back() == s2.back()) {
        return solve(s1.substr(0, s1.size() - 1), s2.substr(0, s2.size() - 1));
    }
    return solve(s1, s2.substr(0, s2.size() - 1));
}

If we are considering the string substring complexity as O(1) in trimming the last character, the above algorithm runs at O(NM) time where N and M are the lengths of s1 and s2 string. The space complexity is O(Max(N, M)) due to the stack usage from Recursion.

Two Pointer Algorithm to Check Subsequence String

We can have two pointers one pointing to s1, and another pointing to s2. We greedily match the characters in s2 to the current character in s1. If they match, move both pointers forward to the right. Otherwise just move forward the s2 pointer until we reach the end of the s2. Then we have to check if the pointer of s1 reaches the end of the s1 string.

1
2
3
4
5
6
7
8
9
10

bool solve(string s1, string s2) {
    int i = 0, j = 0;
    while (i < s2.size()) {
        if (s1[j] == s2[i]) {
            j ++;
        }
        i ++;
    }
    return j == s1.size();
}

bool solve(string s1, string s2) {
    int i = 0, j = 0;
    while (i < s2.size()) {
        if (s1[j] == s2[i]) {
            j ++;
        }
        i ++;
    }
    return j == s1.size();
}

The time complexity is O(NM) where N and M are the length for the s1 and s2 string respectively. The space complexity is O(1) constant.

Hey, in Python, you can do this in Pythonic way: Python Function to Check Subsequence

String Subsequence Algorithms:

• Teaching Kids Programming – Is Subsequence Algorithm via Recursion (Greedy)
• Teaching Kids Programming – Is Subsequence Algorithm via Two Pointer
• The Subsequence Algorithm for Two Strings – How to Check if a String is Subsequence of Another?
• GoLang Function of Checking Is Subsequence
• Algorithms to Check if a String is a Subsequence String of Another String
• in Python, you can do this in Pythonic way: Python Function to Check Subsequence

–EOF (The Ultimate Computing & Technology Blog) —