# Longest Substring Without Repeating CharactersðŸ“¸

--

Given a string `s`

, find the length of the **longest substring** without repeating characters.

**Example 1:**

**Input:** s = "abcabcbb"

**Output:** 3

**Explanation:** The answer is "abc", with the length of 3.

**Example 2:**

**Input:** s = "bbbbb"

**Output:** 1

**Explanation:** The answer is "b", with the length of 1.

**Example 3:**

**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.

**Constraints:**

`0 <= s.length <= 5 * 104`

`s`

consists of English letters, digits, symbols and spaces.

# Java Solutions

I have written 3 different solutions for the same problem, with 3 different time complexities.

**O(nÂ²)**

In the below code im traversing through all the characters in a string, and it is just a basic operation it will take O(n) time (where n is the size of string). But on each loop im changing the loop value if a certain condition comes true, at the end i will still go through all the characters of a string but may not only once. In the worst-case, i have to traverse n-1 characters for a single character which will again take O(n) time, and since this operation will be applied to each character individually, it will take O(n) * O(n) time or O(nÂ²).

## Code

**O(2n)**

The below code is using a sliding window algorithm/technique. Again Outer loop will go through all the characters in a string, so O(n) is the time for that. And the inner loop in the worst case it has to touch every character in a string. Now it may seem that this algorithm also takes O(n) * O(n) or o(nÂ²) time but it isnâ€™t. In the above coding solution, we were modifying the value of the outer loop so in the worst case it has to go through n-1 characters for a single character, but here both the outer and the inner loop has to travel n times through the whole string in the worst case i.e. O(n) + O(n) or (O 2n). Again in the worst case, both inner and outer loops will have to go through all the characters of a string its, not like that inner loop will have to go through all the elements in a string for a single character. No thatâ€™s not the case here.

## Code

**O(n)**

Well here there is only one loop that goes through the whole string only once, so O(n) or linear time.