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 index3
, we have to move thestart
index of our window to1
so we can add the 'a' at index3
to our substring

"Wait...why index + 1?" Well, if we encounter that same character again, we want to be able to move the
Psst...A Map object in JS is an object that remembers the order its keys were passed in.
LineByLine Walkthrough:
function longestSubString(s) {...}

Initialize the variables
max
andstart
with a value of0
andcharMap
using the Map() constructorshow
let max = 0; let start = 0; const charMap = new Map();

Create a
for
loop which will iterate through the length ofs
, initialize variablei
with value of0
.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 ats[i]
.If so, and
start
is smaller than the value incharMap
fors[i]
, we need to shift our window. Movestart
to the index stored incharMap
.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
ori  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 ofmax
, we've found a new longest substring
 In this moment,

Also still in the loop, add
s[i]
tocharMap
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, logfree 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. β₯
Top comments (0)