# 3. Longest Substring Without Repeating Characters (Medium)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

Example 1:

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

Example 2:

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

Example 3:

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

## Solutions

``````class Solution {

// Non-Repeating Character Substring (NRCS)

// This problem solving idea is ingenious that it reduce the time complexity from O(n^2) to O(n)
// with the use of an array which is used to keep track of the last index of the given char.

// Walk through the array, at one point, you visit char x, if you find x not appears before, you
// could deems it as a non-repeating substring. If it occurs previously, there are following two
// situations.

// 1. Take string "abcdefgc" as an example, when pointer locates at the tail char 'c', you will find
// there is another 'c' at index 2, so the max length non-repeating substring is defgc.

// 2. Take string "abcddefgc" as an example, pointer still locates at the tail char 'c', precious 'c'
// at index 2. However, the max length non-repeating substring turns to be defgc. The reason is that
// the counting work starts from the second d because of the prior repeated d.

// To sum up, when you meet a repeating char, it is not a must to start over the counting, which
// depends on the specific cases.

public int lengthOfLongestSubstring(String str) {
if (str == null || str.length() == 0) {
return 0;
}

int len = str.length();

int[] visited = new int[256];

//  Initialize the visited array as -1, -1 is used to indicate that character has not been visited yet.
Arrays.fill(visited, -1);

// length of max NRCS substring
int maxLen = 0;

// previous index
int prevIndex;

// length of current NRCS substring
int curLen = 0;

for (int i = 0; i < len; i++) {
prevIndex = visited[str.charAt(i)];

// Current character is not present in the already processed substring.
if (prevIndex == -1) {
curLen++;
}
// It is not part of the current NRCS, ignore it and increase curLen
else if (i - curLen > prevIndex) {
curLen++;
}
// If the current character is present in currently considered NRCS, then update NRCS
// to start from the next character of the prevIndex.
else {
curLen = i - prevIndex;
}

// Also, when we are changing the NRCS, we should also check whether length of the previous
// NRCS is greater than maxLen or not.
if (curLen > maxLen) {
maxLen = curLen;
}

// update the index of current character
visited[str.charAt(i)] = i;
}

return maxLen;
}
}
``````

## Incorrect Solutions

``````class Solution {

// This solution exceeds the time limit.

// Walk through all the possible length from 2 to s.length(). Use a HashMap to keep the length and
// possible ranges.

public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}

int len = s.length();

Map<String, Integer> visited = new HashMap<>();
for (int i = 0; i < len; i++) {
visited.put(i + "#" + i, 1);
}

// Window size starts from 2 to len
for (int ws = 2; ws <= len; ws++) {

// Iterate the chars from 0, and the window tail should not exceed i+wws-1
for (int i = 0; i < len - ws + 1; i++) {

// Window [i,i+ws-2] is a preceding window that 1 element less than current
// window [i, i+ws-1]. If preceding window contains duplicates, it indicates
// current window also has.

String pw = i + "#" + (i + ws - 2);
if (!visited.containsKey(pw)) {
continue;
}

String cw = i + "#" + (i + ws - 1);

// s.substring(start, end) where end is exclusive

if (!s.substring(i, i + ws - 1).contains(s.charAt(i + ws - 1) + "")) {
// if doesn't contain duplicates, increase the distinct char number
visited.put(cw, visited.get(pw) + 1);
}
}
}

int max = 0;
for (String key : visited.keySet()) {
if (visited.get(key) > max) {
max = visited.get(key);
}
}

return max;
}
}
``````