Solution Explanation: 392. Is Subsequence

This problem asks whether string s is a subsequence of string t. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Approach: Two Pointers

The most efficient approach uses two pointers, one for each string.

1. Initialization: Two pointers, i for s and j for t, are initialized to 0.

2. Iteration: The pointers iterate through the strings. If s[i] and t[j] match, it means we've found the next character of the subsequence in t. Both pointers (i and j) are incremented. If they don't match, only j (the pointer for t) is incremented, searching for the next potential match.

3. Termination: The loop continues until either i reaches the end of s or j reaches the end of t.

4. Result: If i reaches the end of s, it implies that all characters of s were found in t in the correct order, so s is a subsequence of t, and the function returns true. Otherwise, s is not a subsequence, and the function returns false.

Time and Space Complexity Analysis

• Time Complexity: O(m + n), where m is the length of s and n is the length of t. In the worst case, we iterate through both strings once.

• Space Complexity: O(1). We only use a constant amount of extra space for the pointers i and j.

Code Implementation in Various Languages

The following code demonstrates the two-pointer approach in several programming languages:

Python3

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

Java

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

C++

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
};

JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    let i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] === t[j]) {
            i++;
        }
        j++;
    }
    return i === s.length;
};

Go

func isSubsequence(s string, t string) bool {
	i, j := 0, 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == len(s)
}

(Other languages like C#, TypeScript, Rust, etc., would follow a similar structure.)

This two-pointer approach provides an efficient solution to the subsequence problem with linear time complexity, making it suitable even for large input strings.