AlgoDaily - Is A Subsequence

Is A Subsequence (Medium)

Good morning! Here's our prompt for today.

You may see this problem at Amazon, Stripe, Lyft, Splunk, Walmart Labs, Gitlab, Carta, Invision, Opendoor, Bosch Global, and Seagate.

Given two strings, one named sub and the other str, determine if sub is a subsequence of str.

JAVASCRIPT

1const str = "barbell"
2const sub = "bell"
3isASubsequence(sub, str);
4// true

For the sake of the exercise, let's assume that these strings only have lower case characters.

What is subsequence? You can think of it as a substring, but the letters don't have to be adjacent. It is formed from the base string by deleting some or none of the characters without affecting the relative positions of the other letters. So this also works:

JAVASCRIPT

1const str = "chicken"
2const sub = "hen"
3isASubsequence(sub, str);
4// true

Constraints

Length of both the strings <= 100000
The strings will contain only alphanumeric characters (a-z , A-Z, 0-9)
The strings can be empty
Expected time complexity : O(n)
Expected space complexity : O(1)

xxxxxxxxxx
​
 
var assert = require('assert');
​
/**
 *  @param {string} sub
 *  @param {string} str
 *  @return {boolean}
 */
function isASubsequence(sub, str) {
  // fill this in
  return true;
}
​
try {
  assert.deepEqual(isASubsequence('c', 'co'), true);
​
  console.log('PASSED: ' + "isASubsequence('c','co') should return true");
} catch (err) {
  console.log(err);
}
​
try {
  assert.deepEqual(isASubsequence('liblu', 'egi'), false);
​
  console.log('PASSED: ' + "isASubsequence('liblu','egi') should return false");
} catch (err) {
  console.log(err);
}

OUTPUT

Results will appear here.