🎨Now live: Try our Free AI Image Generation Feature

Intuition
To determine if a string s
is a subsequence of another string t
, we need to check if all characters of s
appear in t
in the same order. This means we can "skip" characters in t
but must match all characters in s
sequentially. By iterating through both strings simultaneously and ensuring that each character in s
finds a matching character in t
in the correct order, we can verify if s
is a subsequence of t
.
Approach
- Initialize Indices:
Start with two indices, one for each string (
sIndex
fors
andtIndex
fort
), both set to 0. - Iterate Through Strings:
Use a while loop to iterate through both strings:
- If the current character of
s
(s[sIndex]
) matches the current character oft
(t[tIndex]
), incrementsIndex
. - Always incrementtIndex
to continue checking the next character int
. - Check Completion: After the loop, if
sIndex
has reached the length ofs
, it means all characters ins
were found int
in the correct order, so returntrue
. Otherwise, returnfalse
.
Complexity
Time Complexity:
O(n), where n
is the length of the string t
. In the worst case, we may have to traverse the entire string t
to determine if s
is a subsequence.
Space Complexity:
O(1), as we only use a constant amount of extra space for the indices.
Code
C++
class Solution {
public:
bool isSubsequence(string s, string t) {
int sIndex = 0, tIndex = 0;
while (sIndex < s.length() && tIndex < t.length()) {
if (s[sIndex] == t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex == s.length();
}};
Python
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
s_index, t_index = 0, 0
while s_index < len(s) and t_index < len(t):
if s[s_index] == t[t_index]:
s_index += 1
t_index += 1
return s_index == len(s)
Java
class Solution {
public boolean isSubsequence(String s, String t) {
int sIndex = 0, tIndex = 0;
while (sIndex < s.length() && tIndex < t.length()) {
if (s.charAt(sIndex) == t.charAt(tIndex)) {
sIndex++;}
tIndex++;}
return sIndex == s.length();
}}
JavaScript
var isSubsequence = function (s, t) {
let sIndex = 0, tIndex = 0;
while (sIndex < s.length && tIndex < t.length) {
if (s[sIndex] === t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex === s.length;
};