DEV Community

Cover image for LeetCode Challenge: 392. Is Subsequence - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

1 1 2 1 1

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".
Enter fullscreen mode Exit fullscreen mode

Example 2

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

πŸ† 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;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” 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"

Is Subsequence
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;
}

Enter fullscreen mode Exit fullscreen mode

πŸ”‘ 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]
}
Enter fullscreen mode Exit fullscreen mode

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


Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up