interview-questions/arrays-and-strings/longest_substring.py

# Given a string, find the length of the longest substring without repeating characters.
# Time complexity: worst O(n^2), best O(n). Using hash table to check unique
# reduces to always O(n^2)
# Space complexity: O(n/2)

import pytest

def test_longest_substring():
    cases = ['a', 'aaaa','pwdkee', 'asdfghjkl']
    expected = [1, 1, 5, 9]
    for c,e in zip(cases,expected):
        assert longest_substring(c) == e

def longest_substring(s):
    len_s = len(s)
    if len_s <= 1:
        return len_s
    len_longest = 0
    sub_str = []
    for i in range(len_s):
        for j in range(i,len_s):
            if s[j] not in sub_str:
                sub_str.append(s[j])
            else:
                i = j
                if len(sub_str) > len_longest:
                    len_longest = len(sub_str)
                    sub_str = []
                break
    return len_longest