Is Subsequence #392

Two Pointers Easy

Python Java C++

def isSubsequence(s, t):
    i, j = 0, 0

    while j < len(t) and i < len(s):
        if s[i] == t[j]:
            i += 1
        j += 1

    return i == len(s)

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;

        // Iterate through both strings
        while (j < t.length() && i < s.length()) {
            if (s.charAt(i) == t.charAt(j)) 
                i++; // Move pointer for `s` if characters match
            j++; // Always move pointer for `t`
        }

        // Check if all characters in `s` were matched
        return i == s.length();
    }
}

#include 
using namespace std;

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0, j = 0;

        // Iterate through both strings
        while (j < t.size() && i < s.size()) {
            if (s[i] == t[j]) 
                i++; // Move pointer for `s` if characters match
            j++; // Always move pointer for `t`
        }

        // Check if all characters in `s` were matched
        return i == s.size();
    }
};

Problem Statement

Given two strings `s` and `t`, return `true` if `s` is a subsequence of `t`, or `false` otherwise.

Detailed Explanation

Approach

This problem is solved using the two-pointer technique. The key idea is to iterate through `t` and use a pointer `i` to track characters in `s`. Each time a character in `t` matches the current character in `s`, move the pointer in `s`. If all characters in `s` are matched by the end of `t`, `s` is a subsequence of `t`.

Key Concepts

1. Two-Pointer Technique: Use two pointers to traverse both strings simultaneously.
2. Character Matching: Increment the pointer for `s` only when a match is found.

Algorithm Steps

1. Initialize two pointers `i` and `j` to `0`.
2. Iterate through `t` using the pointer `j`:
   • If `s[i] == t[j]`, increment `i` to match the next character in `s`.
   • Always increment `j` to move through `t`.
3. After the loop, check if `i == len(s)`. If true, all characters in `s` are matched, so return `true`. Otherwise, return `false`.

Time and Space Complexity

• Time Complexity: O(n + m)
  • n is the length of `s`.
  • m is the length of `t`.
  • Each string is traversed at most once.
• Space Complexity: O(1)
  • No additional space is used.

Why This Works

The two-pointer approach efficiently matches characters in `s` with `t` while ensuring no unnecessary iterations. By incrementing the pointers appropriately, all possible matches are considered with minimal overhead.

Edge Cases

• `s` is empty: Always return `true` (empty string is a subsequence of any string).
• `t` is empty: Return `false` unless `s` is also empty.
• `s` is longer than `t`: Return `false`.
• All characters in `s` appear in `t` in order: Return `true`.

Common Mistakes

• Not handling empty strings correctly.
• Incorrectly moving pointers for `s` and `t`.
• Not checking the final value of `i` against `len(s)`.