Разделить слово на части

@gray621 · Регистрация: 14.01.2021

Студворк — интернет-сервис помощи студентам

Нужно разделить число на максимальное число частей так, чтобы каждая буква встречалась только в одной части.
из arsegg получится a r s e gg, из assembler получится не ass embler, но a ss emble r. Из remember получится remember.

Вот мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
word = input()
output = []
current_part = ""
 
i = 0
while i < len(word):
    letter = word[i]
    while letter in word[i:] and i < len(word):
        current_part = current_part + word[i]
        i += 1
        continue
    else:
        output.append(current_part)
        current_part = ""
 
print(*output)

Но он не работает на вот таких словах

страстность
получается: страстнос т ь
должно: страстност ь

ротмистрство
получается: ротмистр с т в о
должно: ротмистрство

Алгоритм берет букву как проверочную и проверяет, есть ли она дальше в слове. Если она дальше есть, то в текущую часть добавляется текущая буква слова. Если её дальше нет, то часть добавляется в список и обнуляется, и алгоритм выполняется заново. Но проблема в том, что буквы, которые в части слова между проверочными буквами, могут повторяться потом.

@Arsegg · 02.04.2021, 23:09

Не по теме:

Сообщение от gray621

arsegg получится a r s e gg

Кликните здесь для просмотра всего текста

По теме: ничего не понятно.

@gray621 · 02.04.2021, 23:24 **[ТС]**

Arsegg, Нужно разделить слово на части. Каждая буква слова встречается только в одной из частей.
Пример assembler
В слове assembler множество букв - a, s, e, m, b, l, r
Нужно, чтобы каждая из этих букв встречалась только один раз во всех частях.
Поэтому получается: a ss emble r (буква a встречается только в первой части, буква s только во второй части, буквы e, m, b, l встречаются только в третьей части, буква r встречается только в четвёртой части)

Пример arsegg
получается a r s e gg, т.к. буква a встречается только в первой части, буква r только во второй части и т.д.
если бы было arsegga, то была бы только одна часть arsegga, т.к. нужно чтобы каждая буква встречалась во всех частях ровно один раз. Если разделить на arsegg a, то буква a будет встречаться в 2 частях, что неправильно, поэтому arsegga.

Добавлено через 36 секунд
А и нужно разделить на максимальное кол-во частей

@Arsegg · 03.04.2021, 00:26

Как-то так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import Counter
 
def solution():
    word = input()
    letters = Counter(word)
    result = [[]]
    for letter in word:
        letters[letter] -= 1
        if letters[letter]:
            result[-1].append(letter)
        else:
            if any(letters[c] for c in result[-1]):
                result[-1].append(letter)
            else:
                result[-1].append(letter)
                result.append([])
    print(*map("".join, result))
 
if __name__ == "__main__":
    solution()

@iSmokeJC · 03.04.2021, 00:30

Не по теме:

Боже! Кто выдумывает такую дичь?..

@Arsegg · 03.04.2021, 00:31

Оптимизированная версия:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import Counter
 
def solution():
    word = input()
    letters = Counter(word)
    result = [[]]
    for letter in word:
        letters[letter] -= 1
        result[-1].append(letter)
        if all(letters[c] == 0 for c in result[-1]):
            result.append([])
    print(*map("".join, result))
 
if __name__ == "__main__":
    solution()

@gray621 · 03.04.2021, 12:11 **[ТС]**

Arsegg, как-то можно исправить мой вариант?

@Arsegg · 03.04.2021, 12:26

Сообщение от gray621

как-то можно исправить мой вариант?

Никак. Разбирайся))
P. S. collections.Counter я точно не стану переписывать в dict.
/upd
Да и твой алгоритм работает за O(N ^ 2). Так, между делом, даже если его довести до ума - смысла в нем мало.

@gray621 · 04.04.2021, 14:19 **[ТС]**

Arsegg, Я исправил свой вариант. Мне кажется это костыль, но теперь всё работает.

Python
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
word = input()
output = []
current_part = ""
i = 0
 
while i < len(word):
    letter = word[i]
    while letter in word[i:] and i < len(word):
        current_part = current_part + word[i]
        i += 1
        continue
    else:
        changes = True
        while changes:
            changes = False
            for j in range(1, len(current_part)):
                if i < len(word) and len(current_part) > j:
                    letter = current_part[j]
                    while letter in word[i:] and i < len(word):
                        current_part = current_part + word[i]
                        changes = True
                        i += 1
                        continue
        output.append(len(current_part))
        current_part = ""
 
print(*output)

В первом while внутри while создаётся основная часть слова
В else идёт проверка букв в этой части на наличие дальше в слове. while changes для проверки были ли добавлены буквы и если да, то проверка идёт опять и т.д. пока не будет изменений. Я думаю это быстрее, чем O(n**2)

@eaa · 04.04.2021, 14:53

Arsegg, ну у вас тоже не O(n) даже не O(n*logn) ближе к O(n^2) все равно, хотя задаче решается за O(n).

@Arsegg · 04.04.2021, 14:54

Сообщение от eaa

ну у вас тоже не O(n) даже не O(n*logn) ближе к O(n^2) все равно, хотя задаче решается за O(n).

O(N), внимательно посмотрите алгоритм.

@eaa · 04.04.2021, 15:04

Arsegg, как скажете. пусть будет O(n). значит я ошибся

.

@Arsegg · 04.04.2021, 15:19

Сообщение от eaa

как скажете. пусть будет O(n). значит я ошибся.

Ок, вызов принят:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import Counter
 
def solution():
    word = input()
    letters = Counter(word)  # В среднем O(N) - я думаю, это очевидно (худший случай, когда кривой хеш у строк опустим)
    result = [[]]
    for letter in word:  # O(N) - аналогично
        letters[letter] -= 1
        result[-1].append(letter)
        if all(letters[c] == 0 for c in result[-1]):  # O(M), M <= N
            result.append([])
    # Суммарно, будет не более N частей (result[i]) - O(M) => Общая асимтотика O(N)
    print(*map("".join, result))
 
if __name__ == "__main__":
    solution()

@eaa · 04.04.2021, 15:21

Python
1
word = 'a'+'b'*1000000 + 'a' +'cc'

у меня около 11 секунд без вывода считает.
видимо 1 миллион операций для python'a много

@Arsegg · 04.04.2021, 15:30

Сообщение от eaa

видимо 1 миллион операций для python'a много

Да, Python может "сгрызсть" только 10 ^ 5 за разумное время (<10 сек). А это линейный алгоритм.

@eaa · 04.04.2021, 15:37

Сообщение от Arsegg

А это линейный алгоритм.

буду знать на будущее. Спасибо.
мое решение на за O(n) на этом примере работает за 0.3 секунды. ваше решение O(n) 11.5 секунд.
где подвох?!

@Arsegg · 04.04.2021, 15:51

Сообщение от eaa

мое решение на за O(n) на этом примере работает за 0.3 секунды.

Я ж не знаю, какое у вас решение.

@gray621 · 04.04.2021, 16:51 **[ТС]**

eaa, Arsegg, не парьтесь особо, это же просто яндекс. Кстати eaa, пришлите своё решение, пожалуйста

Добавлено через 1 минуту
кстати, а за сколько моё решение?

Добавлено через 2 минуты
вот решение Gdez,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
word = input()
output = []
i = 0
while i < len(word):
    a = i
    b = word.rfind(word[i])
    j = 1
    if b > a:
        j = a+1
        while j < b:
            t = word.rfind(word[j])
            b = max(b, t)
            j += 1
    output.append(b-a+1)
    i += b-a+1
print(*output)

Спасибо, [nick]Gdez/nick].
Насколько быстрое решение Gdez?

Добавлено через 4 минуты
У меня костыль в решении видимо...

@eaa · 04.04.2021, 22:06

Да я то не парюсь))
Просто это классический пример когда программист игнорирует изучение алгоритмов.
И доказывает что белое это чёрное

Стандартная задача за O(n).
Свое решение я описал здесь:
Запруды

@Arsegg · 04.04.2021, 22:42

Сообщение от eaa

у меня около 11 секунд без вывода считает.
видимо 1 миллион операций для python'a много

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
In [1]: from collections import Counter
    ...:
    ...: def solution(word):
    ...:     letters = Counter(word)
    ...:     result = [[]]
    ...:     for letter in word:
    ...:         letters[letter] -= 1
    ...:         result[-1].append(letter)
    ...:         if all(letters[c] == 0 for c in result[-1]):
    ...:             result.append([])
    ...:     yield from map("".join, result)
    ...:
 
In [2]: word = 'a'+'b'*1000000 + 'a' +'cc'
 
In [3]: timeit solution(word)
464 ns ± 5.04 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

ЧЯДНТ?

Новые блоги и статьи Все статьи Все блоги /
изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

@gray621 63 / 52 / 11 Регистрация: 14.01.2021 Сообщений: 406
	02.04.2021, 23:24 [ТС]
	Arsegg, Нужно разделить слово на части. Каждая буква слова встречается только в одной из частей. Пример assembler В слове assembler множество букв - a, s, e, m, b, l, r Нужно, чтобы каждая из этих букв встречалась только один раз во всех частях. Поэтому получается: a ss emble r (буква a встречается только в первой части, буква s только во второй части, буквы e, m, b, l встречаются только в третьей части, буква r встречается только в четвёртой части) Пример arsegg получается a r s e gg, т.к. буква a встречается только в первой части, буква r только во второй части и т.д. если бы было arsegga, то была бы только одна часть arsegga, т.к. нужно чтобы каждая буква встречалась во всех частях ровно один раз. Если разделить на arsegg a, то буква a будет встречаться в 2 частях, что неправильно, поэтому arsegga. Добавлено через 36 секунд А и нужно разделить на максимальное кол-во частей 0

@iSmokeJC
	03.04.2021, 00:30
	Не по теме: Боже! Кто выдумывает такую дичь?.. 1

@gray621 63 / 52 / 11 Регистрация: 14.01.2021 Сообщений: 406
	03.04.2021, 12:11 [ТС]
	Arsegg, как-то можно исправить мой вариант? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	04.04.2021, 14:53
	Arsegg, ну у вас тоже не O(n) даже не O(n*logn) ближе к O(n^2) все равно, хотя задаче решается за O(n). 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	04.04.2021, 15:04
	Arsegg, как скажете. пусть будет O(n). значит я ошибся. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	04.04.2021, 22:06
	Да я то не парюсь)) Просто это классический пример когда программист игнорирует изучение алгоритмов. И доказывает что белое это чёрное Стандартная задача за O(n). Свое решение я описал здесь: Запруды 0

Разделить слово на части

Решение