Algo Logging: the Longest Substring of Unique Characters in JavaScript
Tags: algorithms, javascript, beginners, tutorial
Published: 2021-10-08 20:35:16

Recently, I've been meeting with some peers to practice algorithms. We get together once a week to solve a couple problems and discuss our individual solutions, patterns, and best practices.

After our sessions, I take the final, optimized solution of the problems we've solved and add extensive console logs explaining how the solution works and share the result with my peers.

I've decided that this labor of love could possibly benefit others, so, here is the first of at least a few posts on some common algorithms, their solutions, and the logs I've written that explain them. 

This week, we'll start with the __Longest Substring of Unique Characters__ problem.

If you'd like, you can attempt the problem yourself, first:
* [LeetCode](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
*  [CodeWars](https://www.codewars.com/kata/simple-fun-number-396-find-the-longest-substring-consisting-of-unique-characters/)

___
## The Problem

The __Longest Substring of Unique Characters__, also called __The Longest Substring Without Repeating Characters__, is as follows:

> *Given a string* `s`*, return the length of the longest substring consisting of unique characters.*

__Example__
> `s` = "ababcccabcdefbc"
> output = 6 (length of "...abcdef...")

So, where do we start?
___

### The Approach: Sliding Window

For those unfamiliar, the sliding window technique is a method for solving certain algorithms, particularly those that request a 'sub-' version of an array or string. While there are certainly more than a few ways to solve such problems, sliding window *usually* presents a reduced time complexity to other solutions.

In this particular instance, using sliding window allows us to achieve linear time (O(n)), as opposed to a brute force approach using multiple nested for loops with O(n^3). Woof.

Even if you've never seen sliding window used or heard of time complexity and Big O notation, don't fret! We're going to walk through this problem one iteration at a time.

#### Variables Used:

+ `max` - tracks the longest length seen (solution)
+ `start` - an integer pointing to the starting index of our sliding window
+ `i` - an integer pointing to the end of our sliding window as we iterate through the string.
+ `charMap` - a Map* object, storing seen characters and their most recently seen index + 1.
  + __*"Wait...why index + 1?"*__ Well, if we encounter that same character again, we want to be able to move the `start` of our sliding window to _exclude_ the last time we saw it.
  + _EX._ *If we saw 'a' at index `0` and see it again at index `3`, we have to move the `start` index of our window to `1` so we can add the 'a' at index `3` to our substring*



> *Psst...A [Map object](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map) in JS is an object that remembers the order its keys were passed in.*

#### Line-By-Line Walkthrough:

```js
function longestSubString(s) {...}
```

1. Initialize the variables `max` and `start` with a value of `0` and `charMap` using the Map() constructor {% collapsible show %}```js
let max = 0;
let start = 0;
const charMap = new Map();
```{% endcollapsible %}

2. Create a `for` loop which will iterate through the length of `s`, initialize variable `i` with value of `0`. {% collapsible show %}```js
for (let i = 0; i < s.length; i++) {...
``` {% endcollapsible %} 


3. Inside of the loop, create a conditional statement that asks if `charMap` currently contains the character held at `s[i]`. 

     If so, and `start` is smaller than the value in `charMap` for `s[i]`, we need to shift our window. Move `start` to the index stored in `charMap`. {% collapsible show %}```js
   if (charMap.has(s[i])) {
       start = Math.max(charMap.get(s[i]), start);
   }
   ``` + `Math.max` *takes the largest of its arguments.*
{% endcollapsible %} 
4. Still inside the loop, set `max` to whichever is larger: `max` or `i - start + 1`. {% collapsible show %}```js
  max = Math.max(max, i - start + 1);
  ``` {% endcollapsible %} 
  + In this moment, `i` is the end of our current window, `start` is the start, and the +1 corrects for zero indexing to get the max length. If that is bigger than the value of `max`, we've found a new longest substring

7. Also still in the loop, add `s[i]` to `charMap` with it's index, `i`, as it's value. {% collapsible show %}```js
      charMap.set(s[i], i + 1);
  }
  ```{% endcollapsible %} 

8. Once the loop is finished, return 'max'. {% collapsible show %}```js
      return max;
  }
  ```{% endcollapsible %}

___
### Show Me The Logs

Here are my console.logs for this problem.

__For the best experience, view them on [replit](https://replit.com/@raquii/LongestSubStringLogs?v=1), where you can fork it and feed your own string into the function!__

```js

🚀 🚀 LONGEST SUBSTRING OF UNIQUE CHARACTERS STARTING NOW 🚀 🚀 

    📥 s = "ababcbbc"

=================FOR LOOP=================

    --- We are on iteration 1 of 8 ---

    The current Window is "[]ababcbbc"

        🔸 i =  0 
        🔸 start =  0 
        🔸 max =  0 
        🔸 charMap =  Map {}
        🔸 s[i] = 'a'
    
    → Does 'charMap' contain 'a'? 

      ❌ NO: 
        → 'a' will be added to charMap
        → The current window will add 'a'

      🌟 NEW MAX FOUND 🌟 
            max = 1

    → 'a's value in 'charMap' will now equal: 1

=================FOR LOOP=================

    --- We are on iteration 2 of 8 ---

    The current Window is "[a]babcbbc"

        🔸 i =  1 
        🔸 start =  0 
        🔸 max =  1 
        🔸 charMap =  Map { 'a' => 1 }
        🔸 s[i] = 'b'
    
    → Does 'charMap' contain 'b'? 

      ❌ NO: 
        → 'b' will be added to charMap
        → The current window will add 'b'

      🌟 NEW MAX FOUND 🌟 
            max = 2

    → 'b's value in 'charMap' will now equal: 2

=================FOR LOOP=================

    --- We are on iteration 3 of 8 ---

    The current Window is "[ab]abcbbc"

        🔸 i =  2 
        🔸 start =  0 
        🔸 max =  2 
        🔸 charMap =  Map { 'a' => 1, 'b' => 2 }
        🔸 s[i] = 'a'
    
    → Does 'charMap' contain 'a'? 

      ✅ YES:
        → Does the current window contain a?

        ✅ YES:
          ♦ The last index that did NOT contain 'a' was 1 
          ♦ 'start' is at index 0 
          ♦ 'a' is already inside the window.
        
    ⛔ Repeated Character Found in Window ⛔

        The window needs to shift: 
        'start' moved to index 1

    → 'a's value in 'charMap' will now equal: 3

=================FOR LOOP=================

    --- We are on iteration 4 of 8 ---

    The current Window is "a[ba]bcbbc"

        🔸 i =  3 
        🔸 start =  1 
        🔸 max =  2 
        🔸 charMap =  Map { 'a' => 3, 'b' => 2 }
        🔸 s[i] = 'b'
    
    → Does 'charMap' contain 'b'? 

      ✅ YES:
        → Does the current window contain b?

        ✅ YES:
          ♦ The last index that did NOT contain 'b' was 2 
          ♦ 'start' is at index 1 
          ♦ 'b' is already inside the window.
        
    ⛔ Repeated Character Found in Window ⛔

        The window needs to shift: 
        'start' moved to index 2

    → 'b's value in 'charMap' will now equal: 4

=================FOR LOOP=================

    --- We are on iteration 5 of 8 ---

    The current Window is "ab[ab]cbbc"

        🔸 i =  4 
        🔸 start =  2 
        🔸 max =  2 
        🔸 charMap =  Map { 'a' => 3, 'b' => 4 }
        🔸 s[i] = 'c'
    
    → Does 'charMap' contain 'c'? 

      ❌ NO: 
        → 'c' will be added to charMap
        → The current window will add 'c'

      🌟 NEW MAX FOUND 🌟 
            max = 3

    → 'c's value in 'charMap' will now equal: 5

=================FOR LOOP=================

    --- We are on iteration 6 of 8 ---

    The current Window is "ab[abc]bbc"

        🔸 i =  5 
        🔸 start =  2 
        🔸 max =  3 
        🔸 charMap =  Map { 'a' => 3, 'b' => 4, 'c' => 5 }
        🔸 s[i] = 'b'
    
    → Does 'charMap' contain 'b'? 

      ✅ YES:
        → Does the current window contain b?

        ✅ YES:
          ♦ The last index that did NOT contain 'b' was 4 
          ♦ 'start' is at index 2 
          ♦ 'b' is already inside the window.
        
    ⛔ Repeated Character Found in Window ⛔

        The window needs to shift: 
        'start' moved to index 4

    → 'b's value in 'charMap' will now equal: 6

=================FOR LOOP=================

    --- We are on iteration 7 of 8 ---

    The current Window is "abab[cb]bc"

        🔸 i =  6 
        🔸 start =  4 
        🔸 max =  3 
        🔸 charMap =  Map { 'a' => 3, 'b' => 6, 'c' => 5 }
        🔸 s[i] = 'b'
    
    → Does 'charMap' contain 'b'? 

      ✅ YES:
        → Does the current window contain b?

        ✅ YES:
          ♦ The last index that did NOT contain 'b' was 6 
          ♦ 'start' is at index 4 
          ♦ 'b' is already inside the window.
        
    ⛔ Repeated Character Found in Window ⛔

        The window needs to shift: 
        'start' moved to index 6

    → 'b's value in 'charMap' will now equal: 7

=================FOR LOOP=================

    --- We are on iteration 8 of 8 ---

    The current Window is "ababcb[b]c"

        🔸 i =  7 
        🔸 start =  6 
        🔸 max =  3 
        🔸 charMap =  Map { 'a' => 3, 'b' => 7, 'c' => 5 }
        🔸 s[i] = 'c'
    
    → Does 'charMap' contain 'c'? 

      ✅ YES:
        → Does the current window contain c?

        ❌ NO 

    → 'c's value in 'charMap' will now equal: 8
_______________________________________________
  

🏁 🏁 🏁 Final Solution 🏁 🏁 🏁
  
Length of longest substring is 3 
```
___
### Solution

Finally, if you'd like to see a clean, log-free version of the solution, here it is:

{% spoiler View Solution %}
```js
function longestSubString(s) {
  let max = 0;
  let start = 0;
  const charMap = new Map();

  for (let i = 0; i < s.length; i++) {
    if (charMap.has(s[i])) {
      start = Math.max(charMap.get(s[i]), start);
    }

    max = Math.max(max, i - start + 1);
    charMap.set(s[i], i + 1);
  }
  return max;
}
  ```{% endspoiler %}


Thanks for reading and I wish you luck on whatever algorithmic endeavor brought you to this post. ♥