Find the Length of the Longest Substring Without Repeating Characters — Leetcode

Find the Length of the Longest Substring Without Repeating Characters — Leetcode

Sliding Window

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

Find the Length of the Longest Substring Without Repeating Characters — Leetcode

Sliding Window

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


Print Share Comment Cite Upload Translate Updates
APA

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/

MLA
" » Find the Length of the Longest Substring Without Repeating Characters — Leetcode." Leonard Yeo | Sciencx - Tuesday March 15, 2022, https://www.scien.cx/2022/03/15/find-the-length-of-the-longest-substring-without-repeating-characters-leetcode/
HARVARD
Leonard Yeo | Sciencx Tuesday March 15, 2022 » Find the Length of the Longest Substring Without Repeating Characters — Leetcode., viewed ,<https://www.scien.cx/2022/03/15/find-the-length-of-the-longest-substring-without-repeating-characters-leetcode/>
VANCOUVER
Leonard Yeo | Sciencx - » Find the Length of the Longest Substring Without Repeating Characters — Leetcode. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/03/15/find-the-length-of-the-longest-substring-without-repeating-characters-leetcode/
CHICAGO
" » Find the Length of the Longest Substring Without Repeating Characters — Leetcode." Leonard Yeo | Sciencx - Accessed . https://www.scien.cx/2022/03/15/find-the-length-of-the-longest-substring-without-repeating-characters-leetcode/
IEEE
" » Find the Length of the Longest Substring Without Repeating Characters — Leetcode." Leonard Yeo | Sciencx [Online]. Available: https://www.scien.cx/2022/03/15/find-the-length-of-the-longest-substring-without-repeating-characters-leetcode/. [Accessed: ]
rf:citation
» Find the Length of the Longest Substring Without Repeating Characters — Leetcode | Leonard Yeo | Sciencx | 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.

You must be logged in to translate posts. Please log in or register.