Longest Substring Without Repeating Characters📸
Given a string
s, find the length of the longest substring without repeating characters.
Input: s = "abcabcbb"
Explanation: The answer is "abc", with the length of 3.
Input: s = "bbbbb"
Explanation: The answer is "b", with the length of 1.
Input: s = "pwwkew"
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.
0 <= s.length <= 5 * 104
sconsists of English letters, digits, symbols and spaces.
I have written 3 different solutions for the same problem, with 3 different time complexities.
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²).
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.
Well here there is only one loop that goes through the whole string only once, so O(n) or linear time.