## Task Description:

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

\
**Constraints:**

* `0 <= s.length <= 5 * 10^4`
* `s` consists of English letters, digits, symbols, and spaces.

\
**Example 1:**

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

\
**Example 2:**

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

\
**Example 3:**

```java
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
```


---

## Brute force approach

The idea is simple, we fix one letter and iterate over the rest of the string until we encounter a duplicate. We save all the letters in the set, and as soon as we find a duplicate letter, we shift the left border by 1 and start over.

\
This is a simple but inefficient approach.

\
**Complexity:**


1. Time complexity: `O(n*n)`
2. Space complexity:  `O(n)`

\
```java
public int lengthOfLongestSubstring(String s) {
    int max = 0;
    for (int left=0; left<s.length(); stleftart++) {
        Set<Character> set = new HashSet<>();
        for (int right=left; right<s.length(); right++) {
            if (left != right && set.contains(s.charAt(right))) {
                break;
            }
            set.add(s.charAt(right));
         }
         max = Math.max(max, set.size());
    }
    return max;
}
```

\
\
\
 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-5kb3ou0.png)

\
## Optimized approach

The idea of optimization is that we don't want to do only 1 step as soon as we meet a duplicate and start all over again. We will move the left border as long as there is a duplicate.

\
**Complexity:**


1. Time complexity: `O(n)`
2. Space complexity:  `O(n)`

   \

```java
public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int max = 0;
    for (int i=0; i<s.length(); i++) {
         char c = s.charAt(i);
        if (set.contains(c)) {
            while (c != s.charAt(i - set.size())) {
                set.remove(s.charAt(i - set.size()));
            }
        } else {
            set.add(c);
        }
        if (set.size() > max) max = set.size();
    }
    return max;
}
```

\
\
\
 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-zjg3ovp.png)

\
I want to note that I do not store the left border in a separate variable (although it is possible).

Since the left border is only needed when we encounter a duplicate, so I know exactly how many unique characters there were: `set.size()`.

\
Therefore, I can find the left border by the formula:  `i - set.size()`.

The algorithm listed above gives us the following result.

\
 ![](https://cdn.hackernoon.com/images/rOSkQXtq7FclP5kp7uY7HWXRaLv1-7ua3owh.png)

I hope this article helped you understand how to solve this type of problem. I will be glad for your feedback.

\
See you soon! ✌

\


Read My Stories

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

How to Find the Longest Substring without Repeating Characters

Too Long; Didn't Read

@top4ikru

RELATED STORIES