Is Subsequence

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](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

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

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) 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:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/bamfsnOK_HQ" frameborder="0" allowfullscreen></iframe></div>

Code

Java

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();
    }
}

Python

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

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)