Finding the Length of the Longest Substring without Repeated Characters in Python3

Full and complete version.

🎯INTRODUCTION

Finding the length of the longest substring in a given string that does not contain any repeated characters is a common programming problem. It requires an efficient algorithm to solve, and Python provides a straightforward approach to tackle this task. In this article, we’ll explore the problem in detail, discuss the algorithmic approach, and provide a Python implementation.

Photo by Kevin Canlas on Unsplash

💡PBOBLEM STATEMENT

Given a string, our goal is to find the length of the longest substring within it that contains no repeated characters. For example, in the string “abcabcbb,” the longest substring without repeating characters is “abc” with a length of 3.

✓ ALGORITHMIC APPROACH

To solve this problem efficiently, we can use a sliding window approach with a set or a dictionary to keep track of the characters seen so far. Here are the steps of the algorithm:

1. Initialize a variable start to keep track of the start index of the current substring, and a dictionary or set to store the most recent occurrence of each character.
2. Iterate through the string using a pointer i and a loop.
3. At each iteration, check if the current character char is already present in the dictionary or set. If it is, it indicates a repeating character.
4. If a repeating character is found, update the start index to one position after the last occurrence of that character. This will allow us to slide the window to the next position.
5. Update the dictionary or set it with the current character and its index.
6. Calculate the length of the current substring by subtracting the start index from the current index i and adding 1.
7. Track the maximum length seen so far by updating a max_length variable if the current substring length is greater than the previous maximum.
8. Repeat steps 3–7 until the entire string is traversed.
9. Return the max_length as the result.

🐍 PYTHON IMPLEMENTATION

Let’s take a look at the Python code that implements this algorithm:

def lengthOfLongestSubstring(s):
    if len(set(s)) == len(s):
        return len(s)
    
    start = 0
    seen = {}
    max_length = 0
    
    for i, char in enumerate(s):
        if char in seen and seen[char] >= start:
            start = seen[char] + 1
        seen[char] = i
        max_length = max(max_length, i - start + 1)
    
    return max_length

Example Usage:

Now, let’s see the algorithm in action with an example:

string = "abcabcbb"
length = lengthOfLongestSubstring(string)
print(length)  # Output: 3

CONCLUSION

Finding the length of the longest substring without repeated characters is a common programming problem that can be efficiently solved using Python. By maintaining a sliding window and updating the start index whenever a repeated character is encountered, we can achieve an optimal solution. The provided Python implementation offers a straightforward approach to solving this task.

This algorithm and code can be utilized in various scenarios where identifying unique substrings is essential, such as string processing, data analysis, or even interview coding challenges.

By understanding the problem statement, the algorithmic approach, and the Python implementation, you can now confidently tackle similar tasks and apply this knowledge to solve real-world problems efficiently.

In conclusion, the ability to find the length of the longest substring without repeated characters is a valuable skill in your programming toolkit. With the algorithm and code presented here, you have a solid foundation to solve this problem and gain confidence in your Python programming abilities.

If you have any questions or need further clarification, don’t hesitate to ask. I am here to help!