Is Subsequence – LeetCode Solution [Easy]

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).

LeetCode Problem Link

Input

strings[] s, t;

Output

true if s is a subsequence of t, false otherwise

Constraints

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

Sample Input

s = "abc", t = "ahbgdc"

Sample Output

true

Explanation
s can be formed as a subsequence from t: ahbgdc

Solution

This problem could be solved in O(n + m), where n is the length of string t and m is the length of string s, by using a two-pointer technique.

Pseudocode

1. Initialize two indices, indexS for the subsequence s and indexT for the text t.

2. Iterate through each character of t using indexT. For each character in t, if it matches the current character in s that indexS points to, we increment indexS.

3. If indexS reaches the length of s, it means all characters of s have been matched in order in t, and we return true.

4. If we traverse all of t without matching all of s, or if t finishes first, we return false.

Code Implementation

//
//  main.cpp
//  Is Subsequence
//
//  Created by Himanshu on 13/05/24.
//

#include <iostream>
using namespace std;

bool isSubsequence(string s, string t) {
    // Two pointers for indices of s and t
    int indexS = 0, indexT = 0;

    // Process every character of t
    while (indexT < t.size()) {
        // Check if current character of t matches current character of s
        if (t[indexT] == s[indexS]) {
            // Move to the next character in s
            indexS++;
            // If we have matched all characters of s, return true
            if (indexS == s.size()) return true;
        }
        // Always move to the next character in t
        indexT++;
    }

    // If we exit the loop without having matched all of s, return false
    return indexS == s.size();
}

int main() {
    string s = "abc", t = "ahbgdc";
    cout << (isSubsequence(s, t) ? "true" : "false") << endl;
    return 0;
}

Output

true

Time Complexity: O(n), s.length() <= t.length()
Space Complexity: O(1)