How to get the length of a substring with the maximum number of unique characters?

Question

There is a task, completed it partially and stuck. I can not figure out how to organize the implementation of the last 3rd paragraph. I would be very grateful if you help me figure it out.

Task: Write the counter (T) function:

host tuple consisting of Latin alphabet strings, for example, ("ABC", "abc")
leading lines to a single (upper or lower) case defining the number of unique Latin characters for each line
(the string "Aaa" contains only 1 unique character) returns the length of the line with the maximum number of unique characters (if there are several such lines, then the largest of them)

Program Code:

def counter(T): # читаем строку и приводим к нижнему регистру, разбиваем на строки T=str(T) T=T[2:-2] T=T.lower().split("\', \'") length_unic=[] length_str=[] length_max = 0 # изменяем число уникальных символов и длину строк, записываем в список for word in T: length_current = len(word) if length_current > length_max: length_max = length_current length_str.append(length_current) unic = set() for letter in word: unic.add(letter) length_unic.append(len(unic)) # поиск максимального уникального max=0 for i in range(len(length_unic)): if length_unic[i] > max: max = length_unic[i] # измерение длины каждой строки max_len_unic = length_unic[0] for i in range(1,len(T)): if length_unic[i] >= max_len_unic: max_len_unic = length_unic[i] max_len_str = length_str[0] if length_str[i] >= max_len_str: max_len_str = length_unic[i] #print(length_max) print(length_unic) print(length_str) T=('Aa', 'ab', 'AaAa', 'AaAaAa', 'ABBA') counter(T)

Axenow axenow 2,119 four 17 · Accepted Answer · 2018-09-30T04:31:42

I'm not sure that I understood the task correctly until the end, but the solution should be:

 def counter(T): # читаем строку и приводим к нижнему регистру, разбиваем на строки T=str(T) T=T[2:-2] T=T.lower().split("\', \'") length_unic=[] length_str=[] length_max = 0 # изменяем число уникальных символов и длину строк, записываем в список for word in T: length_current = len(word) if length_current > length_max: length_max = length_current length_str.append(length_current) unic = set() for letter in word: unic.add(letter) length_unic.append(len(unic)) # поиск максимального уникального max_uniq=0 for i in range(len(length_unic)): if length_unic[i] > max_uniq: max_uniq = length_unic[i] # измерение длины каждой строки max_len_unic = length_unic[0] for i in range(1,len(T)): if length_unic[i] >= max_len_unic: max_len_unic = length_unic[i] max_len_str = length_str[0] if length_str[i] >= max_len_str: max_len_str = length_unic[i] #print(length_max) print(length_unic) print(length_str) tmp_max = max(length_unic) tmp_res = [[index, len(T[index])] for index, value in enumerate(length_unic) if value == tmp_max] print(max(tmp_res, key=lambda x:x[1])[1]) T=('Aa', 'ab', 'AaAa', 'AaAaAa', 'ABBAbb') counter(T)

And yet - you have created the max variable, although this is an internal function that finds the maximum in the array. I re-named it as max_uniq to make everything work correctly.

Answer 2 · 2018-09-30T09:17:18

According to the question, the problem is solved approximately as follows:

 def counter(T): # это нечто вроде базовой проверки передаваемого функции параметра if 'tuple' != type(T).__name__ or \ 1 in list(map(lambda x: 0 in [c.isalpha() for c in x], T)): print('Переданные функции данные имеют неверный формат.') return # находим количество уникальных символов для каждой из строк кортежа print(list(map(lambda x: len(set(x.lower())), T))) # выводим длину строки с максимальным количеством уникальных символов tmp = list(map(lambda x: len(set(x)), T)) print(len(T[tmp.index(max(tmp))]))

MaxU MaxU 52.3k 6 18 51 · Answer 3 · 2018-09-30T11:47:13

Another solution with the computational complexity O(n) (in one pass):

 def counter(T): d = {} max_uniq = 0 max_len = 0 for i,s in enumerate(T): d[s] = {'len': len(s), 'uniq_syms':len(set(s.lower()))} if d[s]['uniq_syms'] == max_uniq: if d[s]['len'] > max_len: max_len = d[s]['len'] elif d[s]['uniq_syms'] > max_uniq: max_uniq = d[s]['uniq_syms'] max_len = d[s]['len'] return d, max_len d, max_len = counter(T)

result:

 In [27]: max_len Out[27]: 4 In [28]: d Out[28]: {'Aa': {'len': 2, 'uniq_syms': 1}, 'ab': {'len': 2, 'uniq_syms': 2}, 'AaAa': {'len': 4, 'uniq_syms': 1}, 'AaAaAa': {'len': 6, 'uniq_syms': 1}, 'ABBA': {'len': 4, 'uniq_syms': 2}}

Beautiful solution, algorithmically optimal) thanks for the help

How to get the length of a substring with the maximum number of unique characters?

3 answers 3

More articles: