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:

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

Example 2:

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

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

Java
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)
  • 🧺 Space complexity: O(n) - Assuming recursion stack

Method 2 - 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

Java
Right to left
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;
    }
}
Left to Right
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)