Minimalna liczba usunięć, aby uzyskać anagramy

Zadanie 7 z 8 · rozdział 12Trudność: 2 z 3napisyanagramzliczanie

Treść zadania

Wczytaj dwa słowa (mogą mieć różne długości). Oblicz, ile łącznie znaków trzeba co najmniej usunąć z obu słów, aby pozostałe napisy były anagramami (pozostałe napisy mogą też być puste).

Dane wejściowe

  • 1. linia: słowo s1 (małe litery)
  • 2. linia: słowo s2 (małe litery)

Dane wyjściowe

Jedna linia: minimalna łączna liczba usuniętych znaków.

Uwagi

  • Dla każdej litery policz, ile razy występuje w s1 (np. s1.count(litera)) i ile w s2. Nadmiarowe wystąpienia trzeba usunąć, więc wynik to suma wartości $|c_1 - c_2|$ po wszystkich literach występujących w którymkolwiek słowie (np. po literach zbioru set(s1 + s2)).

Przykłady

Wejście
grazyna
razynax
Wyjście
2

Z pierwszego słowa usuwamy g, z drugiego x — zostają anagramy razyna i razyna.

Wejście
kajak
ak
Wyjście
3

Z kajak usuwamy k, j i a — zostaje ka, które jest anagramem ak. Z ak nic nie usuwamy.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 12

Zadania w tym rozdziale dotyczą palindromów (napisów czytanych tak samo od przodu i od tyłu), anagramów (napisów złożonych z tych samych liter w innej kolejności) oraz permutacji liter słowa.

Konwencje wspólne:

  • Każde zadanie jest osobnym programem: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj słowo:”.
  • Napis wczytuj jako całą linię. Spacje mogą w nim wystąpić tylko tam, gdzie treść mówi o zdaniu.
  • Słowo w zdaniu to fragment oddzielony od innych spacjami. Znaki interpunkcyjne (np. . , ! ? ; : -) stojące na początku lub końcu fragmentu nie należą do słowa (kara. → kara), a fragment złożony wyłącznie z interpunkcji nie jest słowem. W Pythonie: fragment.strip(string.punctuation) dla każdego fragmentu z zdanie.split().
  • Gdy zadanie każe ignorować wielkość liter, porównuj napisy np. po zamianie na małe litery (lower()), ale słowa wypisuj w postaci z wejścia (bez interpunkcji z brzegów).
  • Gdy wynikiem jest kilka napisów, wypisz każdy w osobnej linii. Jeśli nie ma żadnego — program nic nie wypisuje.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
abc
bcd
Oczekiwane wyjście
2

Test 2

Nie uruchomiono
Wejście
ab
abc
Oczekiwane wyjście
1

Test 3

Nie uruchomiono
Wejście
abc
cba
Oczekiwane wyjście
0

Test 4

Nie uruchomiono
Wejście
aaaa
bbbb
Oczekiwane wyjście
8

Test 5

Nie uruchomiono
Wejście
kot
pies
Oczekiwane wyjście
7

Test 6

Nie uruchomiono
Wejście
kajak
kotek
Oczekiwane wyjście
6

Test 7

Nie uruchomiono
Wejście
x
yy
Oczekiwane wyjście
3
Uruchom z własnymi danymi