This content originally appeared on Level Up Coding - Medium and was authored by Leonard Yeo
Find the Length of the Longest Substring Without Repeating Characters — Leetcode
Problem
Given a string, find the length of the longest substring without repeating characters.
Examples
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.
Example 4:
Input: "abcade"
Output: 5
Explanation: The answer is "bcade", with the length of 5.
Solution 01
def lengthOfLongestSubstring(s):
if len(s) == 0:
return 0
max_len = 0
for i in range(len(s)):
_map = {}
_map[s[i]] = 1
for j in range(i+1, len(s)):
temp = j
if s[j] not in _map:
_map[s[j]] = 1
else:
break
max_len = max(max_len, len(_map))
return max_len
Time and Space Complexity
- Time Complexity: O(N*N-1)
- Space Complexity: O(D)
Solution 02
def lengthOfLongestSubstring(s):
if len(s) == 0:
return 0
max_len = 0
# map of last index of every character
last_idx = {}
# starting index of current window to calculate max_len
start_idx = 0
for i in range(0, len(s)):
if s[i] in last_idx:
start_idx = max(start_idx, last_idx[s[i]] + 1)
# Update result if we get a larger window
max_len = max(max_len, i-start_idx + 1)
# Update last index of current char.
last_idx[s[i]] = i
return max_len
Illustration
Latest: {}
Index: 0 Current char: a
i: 0 start_idx: 0
max_len: 1
Latest: {'a': 0}
====================
Index: 1 Current char: b
i: 1 start_idx: 0
max_len: 2
Latest: {'a': 0, 'b': 1}
====================
Index: 2 Current char: c
i: 2 start_idx: 0
max_len: 3
Latest: {'a': 0, 'b': 1, 'c': 2}
====================
Index: 3 Current char: a
i: 3 start_idx: 1
max_len: 3
Latest: {'a': 3, 'b': 1, 'c': 2}
====================
Index: 4 Current char: b
i: 4 start_idx: 2
max_len: 3
Latest: {'a': 3, 'b': 4, 'c': 2}
====================
Index: 5 Current char: c
i: 5 start_idx: 3
max_len: 3
Latest: {'a': 3, 'b': 4, 'c': 5}
====================
Index: 6 Current char: b
i: 6 start_idx: 5
max_len: 3
Latest: {'a': 3, 'b': 6, 'c': 5}
====================
Index: 7 Current char: b
i: 7 start_idx: 7
max_len: 3
Latest: {'a': 3, 'b': 7, 'c': 5}
====================
Time and Space Complexity
- Time Complexity: O(N+D). Given N is the number of characters in the string and D is the number of characters in the input string alphabet.
- Space Complexity: O(D)
Takeaways
Thank you for reading this short problem solving question. If anyone knows a better or faster time complexity to solve this question, feel free to comment and feedback. Peace! ✌️
Find the Length of the Longest Substring Without Repeating Characters — Leetcode was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Leonard Yeo
Leonard Yeo | Sciencx (2022-03-15T13:20:52+00:00) Find the Length of the Longest Substring Without Repeating Characters — Leetcode. Retrieved from https://www.scien.cx/2022/03/15/find-the-length-of-the-longest-substring-without-repeating-characters-leetcode/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.