Longest Substring Without Repeating Characters

When working with strings in programming, a common problem is finding the length of the longest substring without repeating characters. This problem is interesting because it requires an efficient approach to navigate through the string and handle potential overlaps or repeated characters. In this blog post, we'll explore a practical solution using JavaScript.

Problem Statement

Given a string s, we need to find the length of the longest substring without repeating characters.

Example

Let's consider a few examples to understand how the "Longest Substring Without Repeating Characters" method works :

Example 1 :
Input : s = "abcabcbb"
Output : 3
Explanation : The answer is "abc", with the length of 3.

Example 2:
Input : s = "bbbbb"
Output :1
Explanation : The answer is "b", with the length of 1.

Example 3:
Input : s = "pwwkew"
Output :3
Explanation : The answer is "wke", with the length of 3.

Solution Approach 🧾

To solve this problem efficiently, we'll use the sliding window technique. The idea is to maintain a "window" of characters that does not contain any repeating characters. We'll move this window through the string, expanding it when we encounter unique characters and contracting it when we hit a repeat.

Let's walk through the solution step by step.

Step-by-Step Implementation

var lengthOfLongestSubstring = function(s) {
  debugger;
  if (s.length === 0) return 0;

  let max = "";
  let iter = "";

  for (let i = 0; i < s.length; i++) {
    if (!iter.includes(s[i])) {
      iter += s[i];
    } else {
      if (iter.length > max.length) {
        max = iter;
      }
      // Start a new iter from the next character after the first occurrence of the repeating character
      iter = iter.slice(iter.indexOf(s[i]) + 1) + s[i];
    }
  }
  if (iter.length > max.length) {
    max = iter;
  }

  return max.length;
};

Explanation

Initialization : We start by checking if the string is empty. If it is, we return 0 because there's no substring. We then initialize two variables: max to store the longest substring found so far, and iter to store the current substring being evaluated.

Iterating Through the String : We loop through each character in the string s.

• Unique Character : If the current character is not in iter, we add it to iter.
• Repeating Character : If the character is already in iter, it means we've encountered a repetition. Before handling the repetition, we check if the current iter is longer than max. If it is, we update max. Then, we adjust iter by removing all characters up to the first occurrence of the repeating character, and start fresh from there.

Final Comparison : After the loop completes, we make a final comparison between iter and max to ensure we've captured the longest substring.

Result : Finally, we return the length of the max substring.

Time Complexity

This solution runs in O(n) time, where n is the length of the string. The sliding window approach ensures that each character is processed at most twice (once when added to iter and once when removed), making it highly efficient.

Conclusion

This problem showcases a common pattern in algorithm design: using a sliding window to efficiently track and adjust a subset of elements (in this case, characters in a string). Understanding and implementing such patterns will make you a stronger programmer, especially when working with strings or arrays.

Feel free to experiment with the code and try different inputs to see how the algorithm performs. Happy coding!