Longest substring in Python

10.2K views

Open Source Your Knowledge, Become a Contributor

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

Задача

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

Решение

Используем хэшмапу, трекая уникальные символы

# 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

Тесты

Используем 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()

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

Задача

Решение

Тесты

Learn Python with 'de Developer'

Basic Introduction to Recursion in Python

PYTHON: BEGINNER QUIZ (10 Questions)

PYTHON STRING METHODS: center(), rjust() and ljust().