Longest substring in Python

tsv
6,221 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Задача

Реализовать функцию принимающую на вход строку и возвращающую самую длинную подстроку состоящую не более чем из двух различных символов.

Решение

Используем хэшмапу, трекая уникальные символы
# k is maximum number of unique chars
def longest_substring(input, k = 2):
if input is None:
return input
start = 0
result = ""
freq = {}
i = 0
while i < len(input):
c = input[i]
if c in freq:
freq[c] += 1
else:
freq[c] = 1
if len(freq) == k + 1:
if i - start > len(result):
result = input[start:i]
while len(freq) > k:
c = input[start]
if freq[c] == 1:
freq.pop(c, None)
else:
freq[c] -= 1
start += 1
i += 1
if len(freq) <= k and len(input) - start > len(result):
return input[start:]
return result
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Тесты

Используем Python assert
from impl import longest_substring
def send_msg(channel, msg):
print("TECHIO> message --channel \"{}\" \"{}\"".format(channel, msg))
def success():
print("TECHIO> success true")
def fail():
print("TECHIO> success false")
def test_case(input, expected):
actual = longest_substring(input)
assert actual == expected, "Running longest_substring('{0}')... Expected {1}, got {2}".format(
input, expected, actual)
def test_longest_substring():
try:
test_case(None, None)
test_case("", "")
test_case("a", "a")
test_case("abc", "ab")
test_case("abcc", "bcc")
test_case("aabbcc", "aabb")
test_case("ababcc", "abab")
test_case("aaabbcc", "aaabb")
test_case("aaaabbccccc", "bbccccc")
success()
except AssertionError as e:
fail()
send_msg("Oops! 🐞", e)
if __name__ == "__main__":
test_longest_substring()
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content