Problem Statement:
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).
Examples:
Example 1:
Input: s = “abc”, t = “ahbgdc”
Output: true
Example 2:
Input: s = “axc”, t = “ahbgdc”
Output: false
Constraints:
0 <= s.length <= 1000 <= t.length <= 104sandtconsist only of lowercase English letters.
Approach:
- Use two pointers
i(for strings) andj(for stringt). - Traverse through
tusingj. - If characters match
(s[i] === t[j]), moveito the next character. - Always move
j - If
ireaches the end ofs, it means all characters ofsare found intin order. - Return true if i === s.length, else false.
Visualisation:
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input:
s = "abc", t = "ahbgdc"
State Transitions:
Note: This is a two-pointer approach checking if string `s` is a subsequence of `t`. Step 1: Initialize → i = 0, j = 0 → s[i] = 'a', t[j] = 'a' → match → increment i → i = 1 → increment j → j = 1 Step 2: → s[i] = 'b', t[j] = 'h' → no match → increment j → j = 2 Step 3: → s[i] = 'b', t[j] = 'b' → match → increment i → i = 2 → increment j → j = 3 Step 4: → s[i] = 'c', t[j] = 'g' → no match → increment j → j = 4 Step 5: → s[i] = 'c', t[j] = 'd' → no match → increment j → j = 5 Step 6: → s[i] = 'c', t[j] = 'c' → match → increment i → i = 3 → increment j → j = 6 (loop ends, as j == t.length)
Final Output: true
Final State: All characters of s were found in t in order. Hence, s is a subsequence of t.
var isSubsequence = function(s, t) {
let i = j = 0;
while(j < t.length) {
if(s[i] === t[j]) {
++i
}
++j;
}
return i === s.length;
};
def isSubsequence(s, t):
i = j = 0
while j < len(t):
if i < len(s) and s[i] == t[j]:
i += 1
j += 1
return i == len(s)
public class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (j < t.length()) {
if (i < s.length() && s.charAt(i) == t.charAt(j)) {
++i;
}
++j;
}
return i == s.length();
}
}
#include <string>
using namespace std;
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while (j < t.length()) {
if (s[i] == t[j]) {
++i;
}
++j;
}
return i == s.length();
}
#include <stdbool.h>
#include <string.h>
bool isSubsequence(char *s, char *t) {
int i = 0, j = 0;
while (j < strlen(t)) {
if (s[i] == t[j]) {
++i;
}
++j;
}
return i == strlen(s);
}
public class Solution {
public bool IsSubsequence(string s, string t) {
int i = 0, j = 0;
while (j < t.Length) {
if (i < s.Length && s[i] == t[j]) {
++i;
}
++j;
}
return i == s.Length;
}
}
