Raquel Román-Rodriguez

Posted on Oct 8, 2021

Algo Logging: the Longest Substring of Unique Characters in JavaScript

#algorithms #javascript #beginners #tutorial

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:

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 in JS is an object that remembers the order its keys were passed in.

Line-By-Line Walkthrough:

function longestSubString(s) {...}

Initialize the variables max and start with a value of 0 and charMap using the Map() constructor
show
```
let max = 0;
let start = 0;
const charMap = new Map();
```
Create a for loop which will iterate through the length of s, initialize variable i with value of 0.
show
```
for (let i = 0; i < s.length; i++) {...
```
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.
show
```
if (charMap.has(s[i])) {
   start = Math.max(charMap.get(s[i]), start);
}
```
- Math.max takes the largest of its arguments.
Still inside the loop, set max to whichever is larger: max or i - start + 1.
show
```
max = Math.max(max, i - start + 1);
```
- 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
Also still in the loop, add s[i] to charMap with it's index, i, as it's value.
show
```
  charMap.set(s[i], i + 1);
}
```
Once the loop is finished, return 'max'.
show
```
  return max;
}
```

Show Me The Logs

Here are my console.logs for this problem.

For the best experience, view them on replit, where you can fork it and feed your own string into the function!


🚀 🚀 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:

View Solution

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

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

DEV Community

Algo Logging: the Longest Substring of Unique Characters in JavaScript

The Problem

The Approach: Sliding Window

Variables Used:

Line-By-Line Walkthrough:

Show Me The Logs

Solution

Top comments (0)

Read next

Error Handling with Express

React Native is here to stay

What is Mina Protocol

How to check if a variable is number in Python