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