Description

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

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

For the solution of this problem. We know that we have to find all characters of the substring s in the string t. So, we can start iterating characters of both strings. If we find the match of characters, we know that we found one of the characters from string s, so we increment its index position and start looking for next character. When we find next character, we will increment this counter again and so on until we run out of all characters from either of the strings. In this case, either we have found all characters or not. To decide whether, we have found all characters, we can check if the index position of i is same as length of substring s using i == sChars.length.

 1class Solution {
 2    public boolean isSubsequence(String s, String t) {
 3        if (s == null || t == null)
 4            return false;
 5        if ((s.length() == 0) || (t.length() == 0))
 6            return true;
 7        int i = 0, j = 0;
 8        char[] sChars = s.toCharArray();
 9        char[] tChars = t.toCharArray();
10        while (i < sChars.length && j < tChars.length) {
11            if (sChars[i] == tChars[j]) {
12                i++; // check for next character in s
13            }
14            j++; // we have to increment j, no matter it maches or not.
15        }
16        return i == sChars.length; // if we have exhausted all character of s, then it is subsequence of t.
17    }
18}

Another similar problem to this might be to find exact subsequence. In this case, we cannot have any other characters in between. This problem might be easier once we have seen above problem.

 1class Solution {
 2    public boolean isExactSubsequence(String s, String t) {
 3        if (s == null || t == null)
 4            return false;
 5        if ((s.length() == 0) || (t.length() == 0))
 6            return true;
 7        int i = 0, j = 0;
 8        char[] sChars = s.toCharArray();
 9        char[] tChars = t.toCharArray();
10        while (i < sChars.length && j < tChars.length) {
11            if (sChars[i++] != tChars[j++]) {
12                return false;
13            }
14        }
15        return true;
16    }
17}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 10^9, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?