Algo Logging: the Longest Substring of Unique Characters in JavaScript

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 …


This content originally appeared on DEV Community and was authored by Raquel Román-Rodriguez

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)
  • charMap - a Map* object, storing seen characters with the most recent index that does NOT contain that character
    • (eg. s[1] = 'a', we will store 'a' with a value of 2)
  • start - an integer pointing to the starting index of our current window
  • i - an integer pointing our index in our loop

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) {...}

  1. 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();

  2. 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++) {...

  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. show 

    if (charMap.has(s[i])) {
   start = Math.max(charMap.get(s[i]), start);
}
    • Math.max takes the largest of its arguments.

  4. 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

  5. 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);
}

  6. Once the loop is finished, return 'max'. show 

      return max;
}

Show Me The Logs

If you, like me, are still a little confused about what is happening, fear not: here are the console.logs.

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

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. ♥


This content originally appeared on DEV Community and was authored by Raquel Román-Rodriguez


Print Share Comment Cite Upload Translate Updates
APA

Raquel Román-Rodriguez | Sciencx (2021-10-08T20:35:16+00:00) Algo Logging: the Longest Substring of Unique Characters in JavaScript. Retrieved from https://www.scien.cx/2021/10/08/algo-logging-the-longest-substring-of-unique-characters-in-javascript/

MLA
" » Algo Logging: the Longest Substring of Unique Characters in JavaScript." Raquel Román-Rodriguez | Sciencx - Friday October 8, 2021, https://www.scien.cx/2021/10/08/algo-logging-the-longest-substring-of-unique-characters-in-javascript/
HARVARD
Raquel Román-Rodriguez | Sciencx Friday October 8, 2021 » Algo Logging: the Longest Substring of Unique Characters in JavaScript., viewed ,<https://www.scien.cx/2021/10/08/algo-logging-the-longest-substring-of-unique-characters-in-javascript/>
VANCOUVER
Raquel Román-Rodriguez | Sciencx - » Algo Logging: the Longest Substring of Unique Characters in JavaScript. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/10/08/algo-logging-the-longest-substring-of-unique-characters-in-javascript/
CHICAGO
" » Algo Logging: the Longest Substring of Unique Characters in JavaScript." Raquel Román-Rodriguez | Sciencx - Accessed . https://www.scien.cx/2021/10/08/algo-logging-the-longest-substring-of-unique-characters-in-javascript/
IEEE
" » Algo Logging: the Longest Substring of Unique Characters in JavaScript." Raquel Román-Rodriguez | Sciencx [Online]. Available: https://www.scien.cx/2021/10/08/algo-logging-the-longest-substring-of-unique-characters-in-javascript/. [Accessed: ]
rf:citation
» Algo Logging: the Longest Substring of Unique Characters in JavaScript | Raquel Román-Rodriguez | Sciencx | https://www.scien.cx/2021/10/08/algo-logging-the-longest-substring-of-unique-characters-in-javascript/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts