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