Longest Substring with Distinct Characters Problem Solved with JavaScript

We're gonna have more fun with leetcode today! This problem is considered HARD, however, I'm going to walk you through my solution in a way that is super easy to understand. 🤓

Longest Substring with Distinct Character explained...

Let's say you have a string str that's just a long string of letters. Find the longest substring in str that contains only distinct characters. That means no letter can appear in the substring more than once.

If you've never seen a problem like this before, it can feel a little overwhelming trying to get your head around it. 🤯

Let's break it down into bit size pieces. First step...

How do you check if a string has only unique character ?

There are a bunch of ways of doing this, I'm going to show you how to do it with a hash map - this will make sense later on as we get into the full solution of the problem.

We're going to create a map that counts how often a character occurs in a string.

const str = 'aabbbccccd';
const charFreq = {}; // hashmap counting frequency of characters

for (const char of str) {
    // adding current character to hashmap to count it frequency
    if (!charFreq[char]) charFreq[char] = 0;
    charFreq[char]++;
}

All we're doing here is COUNTING how many times each letter is showing up in str and recording that into an object called charFreq.

After the above code runs charFreq will look like this:

{ a: 2, b: 3, c: 4, d: 1 }

Great! How does this help?

Now think about what charFreq will look like if str contained ONLY distinct characters? Let's say str = 'abcd'. And we ran the above code, then charFreq would be:

{ a: 1, b: 1, c: 1, d: 1 }

EVERY key of charFreq of a distinct string has a value of 1, because each character only occurs once! And since each letter in the string is unique, the length of str is going to be EQUAL to the total number of keys in charFreq.

Let's turn that into a function:

const isStrDistinct = (hashFreq,str) => Object.keys(hashFreq).length === str.length;

Object.keys just returns an array of keys contained in hashFreq. So if...

hasFreq = { a: 1, b: 1, c: 1, d: 1 };

Object.keys(hashFreq);  // => [a, b, c, d]

With the above function isStrDistinct, we can submit the hashFreq of the string, and the string itself. If the function returns true than str only contains distinct characters.

Step 2: Finding the Longest Substring of Distinct Character

isStrDistinct is really going to come in handy on this next step...

testString = 'aaaBBBBBBadfsdBdsabcdefghijkdseweqsBBBa83948BB';

const isStrDistinct = (hash,s) => Object.keys(hash).length === s.length;

// find longest substring that contains only unique characters from str
function LongestUniqueSubStr(str) {
  // starting index
  let start = 0; // starting position of substring
  const charFreq = {}; //hashmap counting frequency of characters
  let substr = '';  // running substring
  let Longest = -Infinity; //size of longest substr
  let longestStr = ''; // longest running substr

  // looping through str , start => beginning of substring
  // and end => ending position of substr
  for (let end = 0; end < str.length; end++) {

    // generating substring
    substr += str[end];

    // adding current character to hashmap to count it frequency
    if (!charFreq[str[end]]) charFreq[str[end]] = 0;
    charFreq[str[end]]++;

    // checking if current substring is unique, if not keep
    // removing first element it is
    while (!isStrDistinct(charFreq,substr) && substr.length > 0) {
      // remove first charactrer of substr
      substr = substr.slice(1);

      //updating charFreq
      charFreq[str[start]]--;
      if (charFreq[str[start]] === 0) delete charFreq[str[start]];

      //incrementing start to reflect to start position
      start++;
    }

    // this point in loop substr is unique, now check it size
    if (substr.length > Longest)  {
      Longest = substr.length;
      longestStr = substr;
    }
  }
  return longestStr;
}

console.log(LongestUniqueSubStr(testString));  // => sabcdefghijk

I know that's a lot to take in! 😬

Let's go through this - it's not as scary as it looks.

We're looking through str checking possible substr, as efficiently as we can. end is the position of the last character of the substr and start is the position of the first character of substr.

This will all begin to make sense as we go through the code.

Let's take a peak at the beginning of the code first:

  // looping through str , start => beginning of substring
  // and end => ending position of substr
  for (let end = 0; end < str.length; end++) {

    // generating substring
    substr += str[end];

    // adding current character to hashmap to count it frequency
    if (!charFreq[str[end]]) charFreq[str[end]] = 0;
    charFreq[str[end]]++;

Here we're looping through the main string str and building outsubstr one letter at a time with substr += str[end]. Then we're also creating our charFreq object that will later help us check if substr contains only distinct characters (or not).

Key logic for this algorithm revealed

Here is where the magic happens:

    // checking if current substring is unique, if not keep
    // removing first element it is
    while (!isStrDistinct(charFreq,substr) && substr.length > 0) {
      // remove first charactrer of substr
      substr = substr.slice(1);

      //updating charFreq
      charFreq[str[start]]--;
      if (charFreq[str[start]] === 0) delete charFreq[str[start]];

      //incrementing start to reflect to start position
      start++;
    }

We're checking if our current substr has only distinct characters. If it does, we continue on. However, if it does NOT, then we start chopping off letters from the BEGINNING of the string until we get a substr with only distinct character!

Why? Because we're only interested in substr with only unique character, so we'll keep looping through until substr has only unique character, even if it means substr gets chopped down to just 1 letter.

NOTE: In the process of chopping down substr we have to update charFreq as well and increment the starting position of our substr start:

      //updating charFreq
      charFreq[str[start]]--;
      if (charFreq[str[start]] === 0) delete charFreq[str[start]];

      //incrementing start to reflect to start position
      start++;

This part of the code is super important. Make sure you understand it! Instead of adding a key to charFreq we're reducing the character count associated with the key. And if the count goes to zero, we REMOVE the key.

Growing and Shrinking substr

We're growing our substr by adding on letters with substr += str[end], and while substr has only distinct characters, everything is GOOD! However, the second substr starts having duplicate characters, we need to start shrinking it with substr = substr.slice(1).

In this process, we're efficiently checking all the potential substr's that could have only unique characters, WITHOUT brute forcing it with an O(N^2) double loop.

Recording the Longest Substr

We can't forget the most important step: recording the longest substr with only distinct character:

  // this point in loop substr is unique, now check it size
    if (substr.length > Longest)  {
      Longest = substr.length;
      longestStr = substr;
    }
  }

Remember: this chunk of code appears AFTER the while loop where we shrunk down substr until it contains only distinct character. It's now safe to check if this substr is the longest one we're encountered thus far, and if so, save it!

Leetcode challenge CONQUERED!!!

😆

Let me know if you have any questions in the comment below?