LeetCode Challenge: 392. Is Subsequence - JavaScript Solution 🚀

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

1. Pointers:

   • Use i to traverse s and j to traverse t.

2. Character Matching:

   • If s[i] === t[j], move both pointers.
   • Otherwise, only move j to check the next character in t.

3. 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

1. Understand Use Cases:

   • Two-pointer is ideal for single queries.
   • Preprocessing is better for multiple queries.

2. Discuss Edge Cases:

   • Empty s ("") → Always true.
   • Characters in s not in t ("xyz", "abc") → Always false.

3. Explain Preprocessing:

   • Highlight how the index map reduces redundant computations.

---

📚 Learn More

Check out the detailed explanation and code walkthrough on my Dev.to post:
👉 Valid Palindrome - JavaScript Solution

Which approach would you choose for your scenario? Let’s discuss! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

---

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!