-
Notifications
You must be signed in to change notification settings - Fork 0
/
problem13.py
43 lines (33 loc) · 1.15 KB
/
problem13.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Good morning! Here's your coding interview problem
# for today.
# This problem was asked by Amazon.
# Given an integer k and a string s,
# find the length of the longest substring that
# contains at most k distinct characters.
# For example, given s = "abcba" and k = 2,
# the longest substring with k distinct characters
# is "bcb"
def longest_substring(s, k):
length = len(s)
longest_string = ''
max_length = 0
if distinct_characters(s) == k and len(s) > max_length:
longest_string = s
max_length = length
for i in range(length):
for j in range(length-1, i, -1):
if distinct_characters(s[i:j]) == k and len(s[i:j]) > max_length:
longest_string = s[i:j]
max_length = len(longest_string)
return longest_string
def distinct_characters(str):
length = len(str)
distinct_chars = []
for i in range(length):
if not distinct_chars.__contains__(str[i]):
distinct_chars.append(str[i])
return len(distinct_chars)
def main():
print(longest_substring('abcba',2))
if __name__ == '__main__':
main()