LeetCode
LeetCode 3: Longest Substring Without Repeating Characters Solution in Python
Learn to implement the Python solution to the “Longest Substring Without Repeating Characters” problem from LeetCode, focusing on the sliding window technique.
In this article, we explore a Python solution to the “Longest Substring Without Repeating Characters” problem from LeetCode, focusing on the sliding window technique. We’ll break down how this approach helps efficiently solve the challenge, highlighting its speed and memory advantages.
class Solution:
def lengthOfLongestSubstring(self, s: str) > int:
m = defaultdict(int)
max_count = 0
i = 0
start = 0
while(i < len(s)):
if s[i] in m and m[s[i]] >= start:
# Move start right after where char was found
start = m[s[i]] + 1
else:
max_count = max(i  start + 1, max_count)
# Record character occurence
m[s[i]] = i
# Iterate through the string
i += 1
return max_count
Understanding the Logic
The provided Python code offers a solution to the “Longest Substring Without Repeating Characters” problem using a sliding window approach with a hash map for tracking character positions. Initially, a defaultdict(int)
named m
is created to store indices of characters as they are encountered. Variables max_count
and start
are set to 0
, where max_count
keeps the length of the longest found substring without repeating characters, and start
indicates the beginning of the current substring. The algorithm iterates through the string s
using a variable i
that serves both as the end pointer of the current substring and the iterator.
During each iteration, the algorithm checks if the current character has been seen before and if it is within the bounds of the current substring (m[s[i]] >= start
). If so, start
is moved right after the last occurrence of the character to maintain the uniqueness of the substring. If the character hasn’t been seen within the current substring, the algorithm updates max_count
to reflect the length of the longest unique substring found so far. The character’s index is updated in m
after each iteration to keep track of the most recent occurrence. The end pointer i
is incremented to extend the substring and continue through the string.
After completing the loop, the algorithm returns max_count
, which holds the length of the longest substring without repeating characters found during the iteration. This method efficiently explores all possible substrings by dynamically adjusting the start and end points based on character repetition, while the hash map enables constanttime lookups and updates for character positions, enhancing the algorithm’s efficiency.
The time and space complexity analysis of my Python solution for the “Longest Substring Without Repeating Characters” LeetCode problem is as follows:
Time Complexity
O(n): The algorithm iterates through the string s
exactly once with a single loop, where n
is the length of the string. During each iteration, it performs a constant number of operations: checking if a character is in the map m
, updating start
, comparing and updating max_count
, and recording the character’s occurrence in m
. Access to the hash map (defaultdict
) for checking existence, updating, or retrieving values occurs in constant time, i.e., O(1), thanks to the hash map’s properties. Therefore, the time complexity is linear with respect to the length of the input string, making it O(n).
Space Complexity
O(min(m, n)): The space complexity is determined by the size of the hash map m
, which stores the indices of characters. In the worst case, if all characters in the string are unique, the hash map will store an entry for each character. However, the size of the hash map is also bounded by the size of the character set. Let m
represent the size of the character set (e.g., the ASCII character set has a size of 128, while the extended ASCII set has 256 characters). Therefore, the space complexity is O(min(m, n)), where n
is the length of the string, and m
is the size of the character set. This complexity takes into account that, in practical scenarios, the hash map will not grow beyond the size of the character set, even if n
becomes very large.
In summary, the solution algorithm for LeetCode’s “Longest Substring Without Repeating Characters” problem achieves linear time complexity, making it efficient for processing strings of varying lengths, and its space complexity is dependent on the smaller of the character set size and the string length, ensuring efficient memory usage.

LeetCode3 weeks ago
LeetCode 2: Add Two Numbers Solution in Python

LeetCode3 weeks ago
LeetCode 1: Two Sum Solution in Python

LeetCode2 weeks ago
LeetCode 7: Reverse Integer Solution in Python

LeetCode2 weeks ago
LeetCode 67: Add Binary Solution in Python

LeetCode2 weeks ago
LeetCode 2942: Find Words Containing Character Solution in Python

LeetCode2 weeks ago
LeetCode 1480: Running Sum of 1D Array Solution in Python

LeetCode2 weeks ago
LeetCode 1512: Number of Good Pairs Solution in Python

LeetCode1 week ago
LeetCode 14: Longest Common Prefix Solution in Python