文字列が変更した際の変更文字数を求める

Question

前提・実現したいこと

以下の問題をPythonを使用して解くのですが、方針が思いつきません。

「会社の看板を作ることになったあなたは、看板に文字列を表示するため、各文字の印刷された小看板を別々に発注して組み合わせることにしました。しかし、発注後に表示する文字列に変更があり、小看板を再発注することになりました。

あなたは再発注する小看板の数を減らすため、共通する文字の小看板を再利用することを考えました。

例えば 文字列が "tokyo" から "osaka" へと変更された場合、共通する o, k の 2 文字の小看板を再利用することで再発注数を 3 つに減らすことができます。
入力として変更前後の文字列の長さおよび文字列自身が与えられます。
この再利用方法で再発注しなければならない最小の小看板の数を出力してください。」

入力される値

入力は標準入力にて以下のフォーマットで与えられます。

n m
s
t

1行目に変更前の文字列の長さ n と 変更後の文字列の長さ m が半角スペース区切りで与えられます。
2行目に変更前の文字列 s が与えられます。
3行目に変更後の文字列 t が与えられます。
入力は合計で 3行 となり、 最終行の末尾に改行が1つ入ります

条件

すべてのテストケースにおいて、以下の条件をみたします。

n, m は整数
1 ≦ n, m ≦ 100000
(sの長さ) = n, (tの長さ) = m
s, t は半角英字小文字のみで構成される文字列

再発注しなければならない最小の小看板の数を整数で出力してください。
最後は改行し、余計な文字、空行を含んではいけません。

入力例

3 5
ant
maven

出力例

3

Comments

[hayataka2049]

問題の出典を示してください

[Ryotarox]

すみません。学校の課題です。

[a_saitoh]

takoがkotaに変わった場合、「0枚」が答えで良いのでしょうか？(位置を変えて再利用を考えに入れるか？)

[Ryotarox]

はい！「0枚」でOKです。

Answer 1

tiitoiさんの回答を参考に、こんなコードにしてみました。

from collections import Counter

str1 = 'ant'
str2 = 'maven'

print(sum((Counter(str2) - Counter(str1)).values()))

Comments

[hayataka2049]

あ、書いてたら解決してた

[Ryotarox]

わざわざ最後まで書いてくださりありがとうございます。自分はforやifを日常的に使うので、そういう方法を教えてくださると勉強になります。

Answer 2

入力の文字数 m, n って入りますかね？

collections.Contour にリストを渡すと、要素とその出現回数の dict-like なオブジェクトが作れます。(str 型はリストにできる)

string = 'antman'
print(Counter(string))  # Counter({'a': 2, 'n': 2, 't': 1, 'm': 1})

これを2つの文字列に適用し、各要素の出現回数を調べます。

from collections import Counter

str1 = 'ant'
str2 = 'maven'

cnt1 = Counter(str1)
cnt2 = Counter(str2)
print('cnt1', cnt1)  # cnt1 Counter({'a': 1, 'n': 1, 't': 1})
print('cnt2', cnt2)  # cnt2 Counter({'m': 1, 'a': 1, 'v': 1, 'e': 1, 'n': 1})

str2 の各文字の出現回数から str1 の各文字の出現回数を減算します。

diff_cnt = cnt2 - cnt1
print('diff_cnt', diff_cnt)  # diff_cnt Counter({'m': 1, 'v': 1, 'e': 1})

Counter.elements() で各要素の出現回数だけ繰り返すイテレータを取得できるので、list() でリスト化します。

diff = list(diff_cnt.elements())
print(diff)

最後に len() でその個数を数えると、それが str2 にあって str1 にない文字数になります。

print(len(diff))  # 3

Comments

[Ryotarox]

なるほど。参考になります。

Answer 3

n, mを使ってないので模範解答では無いかも知れませんが結果は出ますのでご参考までに。

n, m = map(int, input().split(' '))
s = list(input())
t = list(input())
for x in s:
    if x in t:
        t.remove(x)
print(len(t))

入力
3 5
ant
maven

出力
3

Comments

[Ryotarox]

一番簡潔で分かりやすいです。ありがとうございます。

[hayataka2049]

惜しむらくはinやremoveが線形探索するせいでO(nm)になることですね。先に数える方法だとO(n+m)

[opyon]

実行速度大事だと思います。
他の回答でも実行速度倍以上違うのにシンプルだったり回答速いだけでBAついてるの結構ありますよね。
こういう書き方もありますよってつもりで書いてるので私はBA変えて頂いて構いません。

[Ryotarox]

ありがとうございます。参考にします！

Answer 4

# n, m = map(int, input().split(' '))
s = sorted(input())
t = list(input())

d = [x for x in t if not x in s or s.remove(x)]
print(d)
print(len(d))

実行例

参考情報

• Python list subtraction operation

https://stackoverflow.com/questions/3428536/

Comments

[Ryotarox]

少し複雑ですけどありがとうございます。リンクも参考になりました。

Answer 5

Pythonなど不要。そう、シェル芸ならね！

$ cat input.txt
5 5
tokyo
osaka
3 5
ant
maven
$ cat input.txt|xargs -n4|while read a b c d;do comm -13 <(echo $c|grep -o .|sort) <(echo $d|grep -o .|sort)|wc -l|tr -d ' ';done
3
3

Comments

[Ryotarox]

Python使用制限がなければそれでもいいですね。