`Example: Input: "abcca" Output: "abc"`

`Example: Input: "abdecbde" Output: "abdec"`

The problem is similar to sliding window problem where we can have two counters `start`

and `end`

which maintains a window with no character repeated. To identify if a character is in the substring, we can use a **Hashset** that maintains characters visited in that window.

```
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<e;Character>e; set = new HashSet();
int ans = 0, i = 0, j = 0;
while (i <e; n && j <e; n) {
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
```

Another alternate is to use an array which maintains the count of characters visited on the particular index.

```
public int lengthOfLongestSubstring(String s) {
int end = 0, start = 0;
int[] map = new int[128];
int maxLen = 0;
int counter = 0;
while (end < s.length()) {
if (map[s.charAt(end++)]++ > 0)
counter++;
while (counter > 0) {
if (map[s.charAt(start++)]-- > 1)
counter--;
}
maxLen = Math.max(maxLen, end - start);
}
return maxLen;
}
```

The time complexity of the above code is `O(2n) = O(n)`

. The can be further optimized by using HashMap which keeps the latest index of the character.

```
public int lengthOfLongestSubstring(String s) {
Map<e;Character, Integer>e; map = new HashMap();
int max = 0;
for(int i =0 ; start=0, i < s.length(); i++) {
char curr = s.charAt(i);
if (map.containsKey(curr)) {
start = Math.max(start, map.get(curr));
}
max = Math.max(max, i-start+1);
map.put(curr, j+1);
}
return max;
}
```

The **time complexity** of above solution is O(n). To optimize the memory HashMap can be replaced with an array.

**Recommend Reading**

- How java manages Memory?
- Why is it advised to use hashcode and equals together?
- Comparable and Comparator in java
- How to create Singleton class in Java?
- Difference between equals and ==?
- When to use abstract class over interface?
- Difference between final, finally and finalize
- Why is it recommended to use Immutable objects in Java