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
startof our sliding window to exclude the last time we saw it. -
EX. If we saw 'a' at index
0and see it again at index3, we have to move thestartindex of our window to1so we can add the 'a' at index3to 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.
Line-By-Line Walkthrough:
function longestSubString(s) {...}
-
Initialize the variables
maxandstartwith a value of0andcharMapusing the Map() constructorshow
let max = 0; let start = 0; const charMap = new Map(); -
Create a
forloop which will iterate through the length ofs, initialize variableiwith value of0.show
for (let i = 0; i < s.length; i++) {... -
Inside of the loop, create a conditional statement that asks if
charMapcurrently contains the character held ats[i].If so, and
startis smaller than the value incharMapfors[i], we need to shift our window. Movestartto the index stored incharMap.show
if (charMap.has(s[i])) { start = Math.max(charMap.get(s[i]), start); }-
Math.maxtakes the largest of its arguments.
-
-
Still inside the loop, set
maxto whichever is larger:maxori - start + 1.show
max = Math.max(max, i - start + 1);- In this moment,
iis the end of our current window,startis 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]tocharMapwith 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. ♥
Top comments (0)