# 1.5 No-repeat Substring (hard)

#### Problem Statement

Given a string, find the length of the longest substring which has no repeating characters.

**Example 1:**

```
Input: String="aabccbb"
Output: 3
Explanation: The longest substring without any repeating 
characters is "abc".
```

**Example 2:**

```
Input: String="abbbb"
Output: 2
Explanation: The longest substring without any repeating 
characters is "ab".
```

**Example 3:**

```
Input: String="abccde"
Output: 3
Explanation: Longest substrings without any repeating 
characters are "abc" & "cde".
```

#### Solution

This problem follows the Sliding Window pattern and we can use a similar dynamic sliding window strategy as discussed in Longest Substring with K Distinct Characters. We can use a HashMap to remember the last index of each character we have processed. Whenever we get a repeating character we will shrink our sliding window to ensure that we always have distinct characters in the sliding window.

#### Code

```java
public int lengthOfLongestSubstring(String s) {
    int windowStart = 0;
    int maxLen = 0;
    Map<Character, Integer> mp = new HashMap<>();
    for( int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
        char rightChar = s.charAt(windowEnd);
        if(mp.containsKey(rightChar)) {
            windowStart = Math.max(windowStart, mp.get(rightChar) + 1);
        }
        mp.put(rightChar, windowEnd);
        maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
    }
    return maxLen;
}
```

#### Time Complexity

The time complexity of the above algorithm will be O(N) where ‘N’ is the number of characters in the input string.

#### Space Complexity

The space complexity of the algorithm will be O(K) where K is the number of distinct characters in the input string. This also means K<=N, because in the worst case, the whole string might not have any repeating character so the entire string will be added to the HashMap. Having said that, since we can expect a fixed set of characters in the input string (e.g., 26 for English letters), we can say that the algorithm runs in fixed space O(1); in this case, we can use a fixed-size array instead of the HashMap.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dvpr.gitbook.io/coding-interview-patterns/1.-pattern-sliding-window/1.5-no-repeat-substring-hard.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.