LeetCode 3: Longest Substring Without Repeating Characters Solution in Python

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 constant-time 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.