In search of subsequence

Sarunas Medeikis — Fri, 27 Jan 2023 22:52:33 +0000

Consider that you need to find whether two strings are subsequent to each other.

If A is subsequent to B, return true, if not - false

But to begin with.. What is 'subsequence'?
Imagine there is a list (T), a subsequence is a part of that list, but in a certain order(S).
For example, we have a list (T), which consists of letters "ABCD" and we want to find a subsequence, let's pick some letters from our list (T), like "AC" and make a new list just with those letters "AC", that will be our new list (S). To make S a subsequence of T it must have the same order. Check image below, for visual. in our S list we have A and C, and in our T list, A comes first, just like in our S list, also C comes after that. So our S is a subsequence of T.

Now, when we know what IS a subsequence, let's put it in ink about what is NOT a subsequence.

In the image below, everything is essentially the same, except inside our S list I performed a switcheroo, and switched A <-> C , and suddenly, our S is not a subsequence of T anymore.

Another important thing to remember, that for S to be a subsequence of T, they don't have to be consecutive strings, only order has to stay. Meaning that if we take our example from above, and update our T list by adding "CA" at the end, then our S would be a subsequence of T. Check image below, for visualisation.

So... Now that we know about subsequence, we can try to put it into language that our partner can understand. This time, it will be JS.

function isSubsequence(s, t) {
  let pointerS = 0;
  let pointerT = 0;
  while (pointerS < s.length && pointerT < t.length) {
    if (s[pointerS] == t[pointerT]) {
      pointerS++;
    }
    pointerT++;
  }
  return pointerS == s.length;
}

Let's walk through the function.
First, our function(isSubsequence) takes two parameters:

s - a String which has our expected string values.
t - a String which has the letters we will check s against.

Inside our function, we create two variables that we named pointerS and pointerT, and set their value to be 0 (that's the initial position).
Then we enter our while loop. Our loop will continue as long as both pointers are within the bounds of their respective strings (pointerS < s.length && pointerT < t.length).
Inside our loop, we check if the current character of s is equal to the current character of t ( s[pointerS] == t[pointerT] ). If we find that they are equal, it means we have a match! so we can increment our pointerS, so we will start checking another letter inside s. Now, regardless of that, we increment our pointerT, so we move onto the next character in t.
At the end of our while loop, if our pointer is at the end of our s string, it will mean that our s is a subsequence of t, otherwise - tough luck.

Remember - there are many ways in which you can figure it out, the important thing is that you understand what it is. I hoped I managed to bring at least a shred of clarity :) If so - it was worth it.

DEV Community: Sarunas Medeikis

In search of subsequence