## DEV Community is a community of 615,372 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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

``````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)}{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.

## Discussion (0) 