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

Code