392. Is Subsequence

Link

https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=leetcode-75 (opens in a new tab)

Question

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

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

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

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

0 <= s.length <= 100
0 <= t.length <= 10⁴
s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s₁, s₂, ..., s_k where k >= 10⁹, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Answer

JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  //! Edge case
  if (s.length > t.length) return false; //! if len of s is greater than len of t, return false because s cant be a subsequence of t
  `
  Example:
    s='Leetcode'
    t='Code'
    here we are trying to find if 'Leetcode' is a subsequence of 'Code' which is not possible because 'Leetcode' is longer than 'Code'
 
  `;
  const t_length = t.length;
  let subsequence = 0;
  for (let i = 0; i < t_length; i++) {
    if (s[subsequence] === t[i]) {
      // ! if it is matching, increment subsequence
      subsequence++;
    }
  }
  return subsequence === s.length;
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  let found = false;
  let j = 0;
  for (let i = 0; i < t.length; i++) {
    if (t[i] == s[j]) {
      j++;
      if (j == s.length) {
        found = true;
      }
    }
  }
  if (j == s.length) {
    found = true;
  }
 
  return found;
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  let sPointer = 0;
  let tPointer = 0;
 
  while (sPointer < s.length && tPointer < t.length) {
    if (s[sPointer] === t[tPointer]) {
      sPointer++;
    }
    tPointer++;
  }
 
  return sPointer === s.length;
};

Increasing Triplet Subsequence Kids with the Greatest Number of Candies