# Is Subsequence – LeetCode Solution [Easy]

Problem

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

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

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