Day 7 - Longest Substring Without Repeating Characters
Tags: leetcode, python
Published: 2021-01-07 15:42:43

## 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](https://github.com/ruarfff/leetcode-jan-2021)

```python
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

```python
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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/cmta3avmpvgbt3ai89hi.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/qbtj2s04rq9wn9e0oi31.png)

## 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.