Problem

Given two strings s and t, return true if s is a subsequence of t, or false otherwise. OR Given two strings str1 and str2, find if str1 is a subsequence of str2.

Subarrays vs Subsequences vs Subsets Definition

Follow up

  1. Expected time complexity is linear.
  2. Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Examples

Example 1:

1
2

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

1
2

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • s and t consist only of lowercase English letters.

Solution

The idea is simple, we traverse both strings from one side to other side (say from rightmost character to leftmost). If we find a matching character, we move ahead in both strings. Otherwise we move ahead only in str2.

Method 1 - Recursion

Following is Recursive Implementation of the above idea.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

 class Solution {
	 // assuming t is larger, as we are checking - s is subsequence of t
    public boolean isSubsequence(String s, String t) {
        return helper(s, t, s.length(), t.length());
    }
    
    private boolean helper(String s, String t, int m, int n) {
		// Base Cases
		if (m == 0) {
			return true;
		}
		if (n == 0) {
			return false;
		}

		// If last characters of two strings are matching
		if (s.charAt(m - 1) == t.charAt(n - 1)) {
			return helper(s, t, m - 1, n - 1);
		}

		// If last characters are not matching
		return helper(s, t, m, n - 1);
	}
}

Complexity

  • ⏰ Time complexity: O(n) where n is length of string t
  • 🧺 Space complexity: O(n) - Assuming recursion stack

Method 2 - Iterative with 2 pointer technique

To determine if string s is a subsequence of string t, we can use a two-pointer method:

  1. Initialize two pointers i and j to 0, where i will traverse s and j will traverse t.
  2. Iterate through the characters of t using j.
  3. If the current character in t (pointed by j) matches the current character in s (pointed by i), move the pointer i to the next character.
  4. Regardless of whether there’s a match, increment j to check the next character in t.
  5. If i reaches the length of s, all characters of s have been found in t in sequence, and we return true.
  6. If the loop ends and i has not reached the length of s, return false.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public 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();
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i: int = 0
        j: int = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

Complexity

  • ⏰ Time complexity: O(n) where n is the length of t. We potentially traverse all characters of t.
  • 🧺 Space complexity: O(1). We only use a constant amount of extra space for the pointers.

Method 3 - Iterative

The idea is simple, we traverse both strings from one side to another side (say from rightmost character to leftmost). If we find a matching character , we move ahead in both strings. Otherwise, we move ahead only in t.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) {
            return true;
        }
        int i = s.length() - 1;
        for (int j = t.length() - 1; j >= 0 && i >= 0; j--) {
            if(s.charAt(i) == t.charAt(j)) {
                i--;
            }
        }
        return i == -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
	public boolean isSubsequence(String s, String t) {
		int m = s.length(), n = t.length();

		int i = 0; // i - pointer to s, j - pointer on t
		for (int j = 0; i < m && j  <  n; j++) {
			if (s.charAt(i) == t.charAt(j)) {
				i++;
			}
		}
		// If all characters of s were found in t
		return (i == m);
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)