Longest Substring Without Repeating Characters

Finding Longest Substring Without Repeating Characters

Given a string s, your task is to find the length of the longest substring that contains only unique characters, meaning no character repeats within this substring.

A substring is defined as a continuous block of characters within the string, and it must maintain the original order of characters.

For example, in the string “abcabcbb”, the longest substring without repeating characters is “abc”, which has a length of 3.

The goal is to determine the length of such a substring for any given input.

Longest Substring without repeating words

Explanation : The string “xyz” is the longest without duplicate characters.

Constraints:

  • 0 <= s.length <= 1000
  • s may consist of printable ASCII characters.

Finding Longest Substring Solution

Recommendation for Time and Space Complexity – You should aim for a solution with O(n) time and O(m) space, where n is the length of the string and m is the number of unique characters in the string.

Hints for solving problems

Hint 1 :

A brute force solution would be to try the substring starting at index i and try to find the maximum length we can form without duplicates by starting at that index. we can use a hash set to detect duplicates in O(1) time. Can you think of a better way?

Hint 2 :

We can use the sliding window algorithm. Since we only care about substrings without duplicate characters, the sliding window can help us maintain valid substring with its dynamic nature.

There are mainly 3 approach to solve this problem-

  1. Brute Force Method
  2. Sliding Window Method
  3. Sliding Window Mehtod(Optimal)

1. Brute Force Method

Generate all possible substrings, check each substring for unique characters, and keep track of the maximum length.

  • Time complexity: O(n*m)
  • Space complexity: O(m)

where n is the length of the string and m is the total number of unique characters in the string.

Code

2. Sliding Window Method

Use two pointers to create a dynamic window that adjusts based on character repetition. Slide the window by removing characters from the start until all characters in the current window are unique.

  • Time complexity: O(n)
  • Space complexity: O(m)

where n is the length of the string and m is the total number of unique characters in the string.

Code

3. Sliding Window Method(Optimal)

Use a hash set or map to store characters and their positions, adjusting the window efficiently whenever a duplicate is found. This method ensures a time complexity of O(n).

  • Time complexity: O(n)
  • Space complexity: O(m)

where n is the length of the string and m is the total number of unique characters in the string.

Code

More Articles