# Longest Substring Without Repeating CharactersðŸ“¸

--

Question

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

Example 1:

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

Example 2:

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

Example 3:

`Input: s = "pwwkew"Output: 3Explanation: 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.