392. Is Subsequence

EasyTwo PointersStringDynamic Programming

Problem Description

The problem presents us with two strings, s and t. The task is to determine whether s is a subsequence of t. A subsequence of a string is formed by removing zero or more characters from the original string without changing the order of the remaining characters. The function should return true if s can be obtained from t by such a deletion process, otherwise false.

For example, if s is "ace" and t is "abcde", then s is a subsequence of t because you can delete characters 'b' and 'd' from "abcde" without changing the order of the remaining characters to get "ace".

Intuition

To determine if s is a subsequence of t, we iterate through both strings concurrently from the beginning, using pointers. If a character in s matches a character in t, we move forward in both strings. If the characters don't match, we only move forward in t, since we're looking to delete or skip characters from t. When the end of s is reached, it signifies that all characters of s have been matched in t in order, proving that s is a subsequence of t.

We arrive at this solution approach because it efficiently traverses the strings without the need for backtracking. This approach leverages the fact that the relative order of characters in the subsequence must remain consistent with the larger string.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The solution provided uses a simple yet effective algorithm: the two-pointer technique. It involves iterating over both strings s and t simultaneously but independently, with pointers i for string s and j for string t.

Here is how the algorithm is implemented step by step:

Initialize two variables, i and j, to zero. These will act as pointers to the current character being compared in strings s and t, respectively.
Use a while loop to continue the iteration as long as i is less than the length of string s and j is less than the length of string t. This helps in making sure we do not go out of bounds of either string.
Inside the while loop, compare the characters at the current pointers. If s[i] equals t[j], this means the current character in s is matched in t, and we move the pointer i to the next position (i += 1).
Regardless of whether we found a match or not, move the pointer j to the next position (j += 1). This is because even if the current characters do not match, we want to continue looking for the next character of s in the remainder of t.
After the loop, if i is equal to the length of string s, it indicates that all characters of s have successfully been found in t in the correct order, and the function returns true.
If the loop ends because j reaches the end of t but i has not yet reached the end of s, the function returns false because not all characters from s could be matched in t.

By using this approach, the solution is efficient and eliminates the need for extra data structures, making the space complexity O(1) (since the pointers use a constant amount of extra space) and time complexity O(n), where n is the length of string t.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have two strings, s is "axc" and t is "ahbgdc".

Initialize pointers i and j to 0, representing the starting positions in s and t.
Enter the while loop since i < len(s) and j < len(t).
Check if s[i] is equal to t[j] (compare 'a' with 'a'):
- Since they match, increment i to 1 (now s[i] is 'x') and increment j to 1 (now t[j] is 'h').
s[i] is 'x' and t[j] is 'h', they do not match:
- Increment only j to 2 (t[j] is now 'b').
Continue checking:
- s[i] is 'x' and t[j] is 'b' (no match), increment j to 3
- s[i] is 'x' and t[j] is 'g' (no match), increment j to 4
- s[i] is 'x' and t[j] is 'd' (no match), increment j to 5
- s[i] is 'x' and t[j] is 'c' (no match), since 'x' is not found and j has reached the end of t, we exit the loop.
After exiting the loop, we check if i is equal to len(s) which in this case it is not (i is 1 and len(s) is 3).
Since i != len(s), we can conclude that not all characters of s were matched in t, and therefore return false.

Throughout this example, we were able to test whether s is a subsequence of t without needing any extra data structures and by only incrementing the pointers as needed.

Solution Implementation

1class Solution:
2    def is_subsequence(self, subsequence: str, sequence: str) -> bool:
3        # Initialize two pointers for both the subsequence and the sequence
4        subsequence_index = 0
5        sequence_index = 0
6
7        # Iterate over the sequence while there are characters left in both
8        # the subsequence and the sequence
9        while subsequence_index < len(subsequence) and sequence_index < len(sequence):
10            # If the current characters match, move to the next character in the subsequence
11            if subsequence[subsequence_index] == sequence[sequence_index]:
12                subsequence_index += 1
13            # Move to the next character in the sequence
14            sequence_index += 1
15      
16        # Return True if all characters in the subsequence have been matched
17        # This is indicated by subsequence_index pointing to the end of subsequence
18        return subsequence_index == len(subsequence)
19

1class Solution {
2    public boolean isSubsequence(String s, String t) {
3        // Lengths of the strings s and t
4        int lengthS = s.length(), lengthT = t.length();
5      
6        // Initialize pointers for both the strings
7        int indexS = 0, indexT = 0;
8      
9        // Iterate over both strings
10        while (indexS < lengthS && indexT < lengthT) {
11            // Check if the current character of s matches the current character of t
12            if (s.charAt(indexS) == t.charAt(indexT)) {
13                // If they match, move the pointer of s forward
14                ++indexS;
15            }
16            // Move the pointer of t forward
17            ++indexT;
18        }
19      
20        // If indexS is equal to the length of s, all characters of s are found in t in sequence
21        // Therefore, s is a subsequence of t
22        return indexS == lengthS;
23    }
24}
25

1class Solution {
2public:
3    // The function checks if 's' is a subsequence of 't'.
4    bool isSubsequence(string s, string t) {
5        int sLength = s.size(), tLength = t.size(); // Store lengths of both strings.
6        int sIndex = 0, tIndex = 0; // Initialize indices for both strings.
7
8        // Loop through both strings.
9        for (; sIndex < sLength && tIndex < tLength; ++tIndex) {
10            // If characters match, move to the next character in 's'.
11            if (s[sIndex] == t[tIndex]) {
12                ++sIndex;
13            }
14        }
15
16        // If we have gone through the entire 's' string, it is a subsequence of 't'.
17        return sIndex == sLength;
18    }
19};
20

1function isSubsequence(subString: string, mainString: string): boolean {
2    const subStringLength = subString.length;  // Store the length of the subsequence string
3    const mainStringLength = mainString.length;  // Store the length of the main sequence string
4    let subStringIndex = 0;  // Initialize an index to track the current position in subString
5
6    // Loop over the mainString while there are characters left in both strings
7    for (let mainStringIndex = 0; subStringIndex < subStringLength && mainStringIndex < mainStringLength; ++mainStringIndex) {
8        // If characters match, increment the index of the subString
9        if (subString[subStringIndex] === mainString[mainStringIndex]) {
10            ++subStringIndex;
11        }
12    }
13
14    // If subStringIndex equals to subStringLength, all characters of subString were found in order in mainString
15    return subStringIndex === subStringLength;
16}
17

Time and Space Complexity

The time complexity of the code is O(n) where n is the length of string t. This is because the function iterates through each character of t at most once. The pointer i moves only when there is a match in s and t, which does not change the overall linear time complexity with respect to t. It does not iterate more than n times even if every character of s is found in t.

The space complexity of the code is O(1) since no additional space is used that grows with the input size. The only extra memory used is for the two pointers i and j, which use a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know