Strings - Is Subsequence

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: s = "abc", t = "ahbgdc"
Output: true
Explanation: "abc" letters can be found at 0, 2 and 5^th index positions in "ahbgdc"

Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: "axc" is not a subsequence for "ahbgdc" since "x" is not present at all.

Input: s = "axc", t = "ahbgdcx"
Output: false
Explanation: "axc" is not a subsequence for "ahbgdcx", because even though the letters are present but they are not in the sequence.

Solution using two pointers

In this approach, we are going to use two pointers one pointer to point at input string s and another pointer to point at string t and check whether characters in s appear in in the same position int or at greater index.

We will create a function usingTwoPointers that takes input arguments string s and t.
Base case is, if the length of s is greater than length of t, then we can simply return false.
We will create two pointers i and j to track indexes in strings s and t respectively.
Then, we will check characters from each string until i and j did not go out of bounds of s and t.
- If characters at i^th index in s is same as character at j^th index in t, then we will increment i and j. Since we found a matching charcater, we can continue checking next remaining characters.
- Otherwise, just increment j to see if character in s may appear at later index in t.
Finally, at the end check if i reached end index of string s or not, if it reached then s is a subsequence of t, otherwise not.

public class IsSubsequence { /* Using two pointers approach */ static boolean usingTwoPointers(String s, String t) { if(s.length() > t.length()) { return false; } int i = 0; int j =0; while(i<s.length() && j<t.length()) { if(s.charAt(i) == t.charAt(j)) { i++; j++; } else { j++; } } return i == s.length(); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string t length.
Space complexity: O(1) since we are using just indexes i and j to track.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis: