Finding the Longest Unique Substring

Finding the longest substring without repeating characters is a classic problem in computer science and often asked in technical interviews. In this article, we’ll look at two different methods to solve this:

• Brute-force approach
• Sliding window technique (optimized)

Along the way, we'll visualize how each method works and analyze the time and space complexity.

---

Problem Statement

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

Example:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with a length of 3.

---

1. Brute-Force Approach

Check every possible substring and keep track of the longest one with all unique characters.

JavaScript Code

function lengthOfLongestSubstringBruteForce(s) {
  let maxLength = 0;

  for (let i = 0; i < s.length; i++) {
    let seen = new Set();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break;
      seen.add(s[j]);
      maxLength = Math.max(maxLength, j - i + 1);
    }
  }

  return maxLength;
}

console.log(lengthOfLongestSubstringBruteForce("abcabcbb")); // Output: 3

Time Complexity

• Worst-case: ( O(n^2) )

Space Complexity

• ( O(k) ) where ( k ) is the size of the character set (for the Set)

---

2. Sliding Window Approach (Optimized)

Use two pointers to form a window and a set to store characters. Expand the window by moving the right pointer. If a duplicate is found, shrink the window from the left.

JavaScript Code

function lengthOfLongestSubstring(s) {
  let left = 0;
  let right = 0;
  let maxLength = 0;
  const seen = new Set();

  while (right < s.length) {
    if (!seen.has(s[right])) {
      seen.add(s[right]);
      maxLength = Math.max(maxLength, right - left + 1);
      right++;
    } else {
      seen.delete(s[left]);
      left++;
    }
  }

  return maxLength;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3

Time Complexity

• ( O(n) ) – Each character is visited at most twice (once by right, once by left).

Space Complexity

• ( O(k) ) – For the character set

---

Summary

Approach	Time Complexity	Space Complexity
Brute Force	( O(n^2) )	( O(k) )
Sliding Window	( O(n) )	( O(k) )

Using the sliding window approach is recommended for efficiency, especially with longer strings.

---

Thanks for reading! Feel free to test these solutions with your own input strings! Happy coding!