loading...
Cover image for The Longest Substring With No Repeating Characters

The Longest Substring With No Repeating Characters

alisabaj profile image Alisa Bajramovic ・6 min read

Algorithm of the Day (37 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 35 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues

Today's algorithm of the day is one of the most popular ones on Leetcode:

Given a string, find the length of the longest substring without repeating characters.

For example, given the string "abbacda", the output of the function should be 4. The longest substring with no repeating characters is "bacd".

Some approaches to this problem use multiple nested loops, and end up with a huge Time Complexity (sometimes O(n^3)). In this post, I'll be walking through a solution of O(n) time and O(n) space. Because I think this is the kind of problem where the code makes more sense after an explanation, I'll start by using an example with pseudocode, and then code the solution using JavaScript.

In this problem, I'll make a set, and traverse through the given string with two pointers. If the right pointer gets to a character that's already in the string, then the left pointer will be moved over. We'll keep track of the length of the longest substring seen, and return the length at the end.

Using an Example

To start, I'll make an empty set called uniqueSub, and I'll initialize a variable longest which will keep track of the length of the longest substring seen. The inputted string will be "abbac", and I'll start by having two pointers, both on the first letter. j will be the blue circle, i will be the red circle, and the window, or substring, between the two working pointers, will be the opaque purple box in the background.

We will be keeping track of the letter circled by j, the blue circle. Since "a" is not in the uniqueSub set, we can add it to the set. Now, the longest substring is 1.

uniqueSub starts empty, and longest starts at 0. The string is "abbac", and the first character "a" has two circles on it, a red one for `i` and a blue one for `j`. There's an opaque purple box which covers the space between `i` and `j`, so it just covers the first letter. uniqueSub now has "a", and the value of longest is 1.

We'll now move over j, but keep i where it is--how long does this substring go? Again looking at the letter circled by j (blue), we can see that "b" is not in the uniqueSub set, so we can add it. The longest substring is now of length 2.

`j` has moved over, so the purple box now stretches across "a" and "b". uniqueSub is now "a b" and longest is 2.

Now, we've moved j over again, and this time it's on another "b". "b" is already in the uniqueSub set. That means that the substring that started where i is located is no longer unique, so we need to move the window that we're checking over to the right. Therefore, the value at i should be removed from the uniqueSub, because we know that the substring starting at i is no longer unique. Now, uniqueSub just has "b" in it, but the longest value can stay at 2, since that's still the longest substring we've seen.

`j` has moved over, and now the purple box covers "abb". uniqueSub has deleted the letter at spot `i`, so it's now just "b". The longest value still is 2.

i has moved over one spot, and j has stayed at the same place. The substring we're currently working with isn't unique, so we should remove the value at i, therefore making uniqueSub empty, and keep moving i to the right. (Note: longest hasn't changed because it's keeping track of the longest unique substring seen so far. Until we find a unique substring longer than 2, we won't change this value.)

`i` has moved over, and now the purple box covers "bb". The uniqueSub is now empty, and longest is still 2.

Now, i and j are circling the same letter "b", and uniqueSub is empty. We can add "b" to the uniqueSub set.

`i` has moved over, and now `i` and `j` are both on the same letter b. The purple box only covers that letter. uniqueSub is "b", and longest is still 2.

We've moved j one spot over, but kept i where it is. j is pointing at "a", which isn't in the uniqueSub set, so we can add it to the set.

`i` has stayed at the same spot, but `j` has moved forward, so the purple box now covers "ba". The uniqueSub is "ba" and longest is 2.

We've moved j, the right pointer, over again. j is at "c", which is not in the uniqueSub set. We can add it, and now the size of the set is bigger than the previous longest substring we've seen, so we can update longest to be 3. Since j can't move to the right any further, we're at the end of the string, and our function will return 3.

`j` has moved over and `i` is at the same spot. `j` is now on the last letter of the string, "c", and the purple box covers "bac". uniqueSub is "bac" and longest is now 3.

Coding the Solution

The first thing we'll do is initiate a set and a few variables. uniqueSub is a set which will keep track of unique string characters. longest will keep track of the length of the longest unique substring seen. i and j are the two pointers which create a moving window, examining different parts of the string.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  //...
}

Until either i or j hits the end of the string, we should continue checking it, so we can make a while loop. Also, we know we'll want to return the longest value at the end of the function, so we can include it at the bottom.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    //...
  }
  return longest;
}

Now, if the set does not already have the value at j (the right pointer), we can add that value to the set. We can use the .has and .add properties of sets here.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    if (!uniqueSub.has(s[j])) {
      uniqueSub.add(s[j]);
      //...
    } //...
  }
  return longest;
}

After we add the character at j to the set, we can calculate the longest value to equal whichever one is bigger--the previous longest value, or the size of the uniqueSub set. To do this, we can use Math.max, which returns the larger of the values. We also can move j over to the right.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    if (!uniqueSub.has(s[j])) {
      uniqueSub.add(s[j]);
      longest = Math.max(longest, uniqueSub.size);
      j++;
    } //...
  }
  return longest;
}

Finally, if uniqueSub already has the character that j is on, then we know the substring we've been working on is over, and we should move the window over to the right. That means that we need to delete the value at i from the set, and increment i. The reason that we're deleting the value at i is that we don't want to check future characters against it in the set any more.

function lengthOfLongestSubstring(s) {
  let uniqueSub = new Set();
  let longest = 0;
  let i = 0;
  let j = 0;
  while (i < s.length && j < s.length) {
    if (!uniqueSub.has(s[j])) {
      uniqueSub.add(s[j]);
      longest = Math.max(longest, uniqueSub.size);
      j++;
    } else {
      uniqueSub.delete(s[i]);
      i++;
    }
  }
  return longest;
}

I like this "windows" solution because it's pretty efficient in both space and time complexity, but I do think it's pretty difficult to wrap your head around the first few times you see it. Let me know in the comments if you've got any questions or alternate solutions!

Algorithm of the Day (37 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 35 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues

Posted on Jun 1 by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide