392. Is Subsequence

Intuition

To determine if a string s is a subsequence of another string t, we need to check if all characters of s appear in t in the same order. This means we can "skip" characters in t but must match all characters in s sequentially. By iterating through both strings simultaneously and ensuring that each character in s finds a matching character in t in the correct order, we can verify if s is a subsequence of t.

Approach

1. Initialize Indices: Start with two indices, one for each string (sIndex for s and tIndex for t), both set to 0.
2. Iterate Through Strings: Use a while loop to iterate through both strings: - If the current character of s (s[sIndex]) matches the current character of t (t[tIndex]), increment sIndex. - Always increment tIndex to continue checking the next character in t.
3. Check Completion: After the loop, if sIndex has reached the length of s, it means all characters in s were found in t in the correct order, so return true. Otherwise, return false.

Complexity

Time Complexity:

O(n), where n is the length of the string t. In the worst case, we may have to traverse the entire string t to determine if s is a subsequence.

Space Complexity:

O(1), as we only use a constant amount of extra space for the indices.

Code

C++

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

Python

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

Java

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sIndex = 0, tIndex = 0;
        while (sIndex < s.length() && tIndex < t.length()) {
            if (s.charAt(sIndex) == t.charAt(tIndex)) {
                sIndex++;}
            tIndex++;}
        return sIndex == s.length();
    }}

JavaScript

var isSubsequence = function (s, t) {
    let sIndex = 0, tIndex = 0;
    while (sIndex < s.length && tIndex < t.length) {
        if (s[sIndex] === t[tIndex]) {
            sIndex++;
        }
        tIndex++;
    }
    return sIndex === s.length;
};