Problem
Given two strings s and t, return true if s is a subsequence of t. Otherwise, return false.A subsequence is formed by deleting zero or more characters from a string without changing the relative order of the remaining characters.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "abc" t = "ahbgdc"Output
trueSolution
This solution uses the Two Pointer technique. Thei pointer tracks the current character in s, while the j pointer traverses t.
Whenever
s[i] matches t[j], we increment i because that character has been successfully matched. The j pointer is incremented after every comparison to continue scanning t.
If
i reaches the length of s, all characters of s have been found in the correct order, so we return true. Otherwise, s is not a subsequence of t.
class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == s.length();
}
}Complexity
The t string is traversed at most once, resulting in a time complexity ofO(n), where n is the length of t.
The algorithm uses only two pointers, so the extra space complexity is
O(1).