LeetCode Challenge: 392. Is Subsequence - JavaScript Solution 🚀

#javascript #programming #leetcode #interview

Top Interview 150

The Is Subsequence problem is a great challenge that involves iterating through strings to determine if one is a subsequence of the other. Let’s break down LeetCode 392: Is Subsequence and explore both standard and optimized solutions.

🚀 Problem Description

Given two strings s and t:

Return true if s is a subsequence of t.
A subsequence of a string is formed by deleting some characters (or none) from the original string without changing the relative order of the remaining characters.

💡 Examples

Example 1

Input: s = "abc", t = "ahbgdc"  
Output: true  
Explanation: "abc" is a subsequence of "ahbgdc".

Example 2

Input: s = "axc", t = "ahbgdc"  
Output: false  
Explanation: "axc" is not a subsequence of "ahbgdc".

🏆 JavaScript Solution

Approach 1: Two Pointer Technique
Use two pointers to traverse both strings, checking if the characters of s appear in the same order in t.

Implementation

var isSubsequence = function(s, t) {
    let i = 0;
    let j = 0;

    while (i < s.length && j < t.length) {
        if (s[i] === t[j]) {
            i++;
        }
        j++;
    }

    return i === s.length;
};

🔍 How It Works

Pointers:
- Use i to traverse s and j to traverse t.
Character Matching:
- If s[i] === t[j], move both pointers.
- Otherwise, only move j to check the next character in t.
Check Completion:
- If i reaches the end of s, then all characters in s are matched in order in t.

🔑 Complexity Analysis

Time Complexity: O(n+m), where n=s.length and m=t.length.
- Traverse t at most once and s at most once.
Space Complexity: O(1), as no additional data structures are used.

📋 Dry Run

Input: s = "abc", t = "ahbgdc"

Output: true

Follow-Up: Efficient Handling for Multiple s Strings

If there are many incoming s strings to check against a fixed t, preprocess t into an index map for efficient lookup.

Approach 2: Preprocessing t for Faster Matching

Preprocessing: Build a map of character positions for t.

This allows for binary search to quickly locate the next valid position for each character in s.

Optimized Implementation

var isSubsequence = function(s, t) {
    // Preprocess t into a map of character indices
    const indexMap = new Map();

    for (let i = 0; i < t.length; i++) {
        if (!indexMap.has(t[i])) {
            indexMap.set(t[i], []);
        }
        indexMap.get(t[i]).push(i);
    }

    let prevIndex = -1; // Previous matching index in t

    for (let char of s) {
        if (!indexMap.has(char)) return false; // Character not in t

        const positions = indexMap.get(char);
        const nextIndex = binarySearch(positions, prevIndex);

        if (nextIndex === -1) return false; // No valid position found
        prevIndex = nextIndex; // Update to the latest matching index
    }

    return true;
};

// Helper function: Binary search for the next valid index
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left < arr.length ? arr[left] : -1;
}

🔑 Complexity Analysis

Preprocessing:
- Time Complexity: O(m), where m=t.length, to build the index map.
- Space Complexity: O(m), for storing character indices.
Query:
- Time Complexity: O(n⋅logm), where n=s.length and m=t.length. Each character in s requires a binary search in t.

📋 Dry Run

Input: s = "abc", t = "ahbgdc"

Index Map:

{
  a: [0],
  h: [1],
  b: [2],
  g: [3],
  d: [4],
  c: [5]
}

Steps:

Find a → Next valid index is 0.
Find b → Next valid index is 2.
Find c → Next valid index is 5.
Output: true

✨ Pro Tips for Interviews

Understand Use Cases:
- Two-pointer is ideal for single queries.
- Preprocessing is better for multiple queries.
Discuss Edge Cases:
- Empty s ("") → Always true.
- Characters in s not in t ("xyz", "abc") → Always false.
Explain Preprocessing:
- Highlight how the index map reduces redundant computations.