Day 7 - Longest Substring Without Repeating Characters

The Problem

Given a string s, find the length of the longest substring without repeating characters.

Exanple 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: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

My Tests

Link to code

import pytest
from .Day7 import Solution

s = Solution()


@pytest.mark.parametrize(
    "input,expected",
    [
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("ababc", 3),
        ("dvdf", 3),
        ("", 0),
    ],
)
def test_length_of_longest_substring(input, expected):
    assert s.lengthOfLongestSubstring(input) == expected

My Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        size = len(s)
        if size < 2:
            return size

        current_longest = 0
        sub = ""

        for c in s:
            if c not in sub:
                sub += c
                if len(sub) > current_longest:
                    current_longest = len(sub)
            else:
                sub = f"{sub.split(c)[1]}{c}"

        return current_longest

Analysis

My Commentary

This one is the first one this week I would say was actually easy. I got it done in a few minutes. I could certainly optimise it more, particularly the memory usage but am happy to take it easy today instead.

The first step was to check if a string is one character or empty. The answer is 1 or 0 respectively in that case.

I knew I would need to create a counter for the current longest and only replace it when we encounter a longer substring.

We iterate over the string and create a new substring of characters that have not repeated. I am pretty sure we could do this without storing a separate substring. For example, we could store an index instead and compare between the current index and that. Each time we get to a new character, we check if the current substring contains it.

As long as we don't have a repeating character we increment the current_longest number if the current string is longer than that.

If we do encounter a repeating character we need to start a new substring. We need to start this new string at the character after the last repeating character. So if we had a string dv and the next character we encounter is d, we need to create a new substring vd removing the first d.

In the end, we return the current_longest number.