perogram

No.852 連続部分文字列

Quiz

https://yukicoder.me/problems/no/852

AC Code

https://yukicoder.me/submissions/363142

参考

参考2 ngtkanaさん

https://yukicoder.me/submissions/362752

参考3 解説の4

https://yukicoder.me/problems/no/852/editorial

解法

  • 各文字ごとに分けて求めることができます(a, b, c.., zの26種類を別々に求める)

各連続部分文字列について全ての文字の種類を含んでいるものと仮定します

  • |s|=6の場合を考えてみよう
  • s = "aaaaaa" と仮定すると、部分文字列のとり方は、6+5+4+3+2+1
  • 一般に N * (N+1) / 2

f:id:peroon:20190727023236j:plain

  • 実際はaxxaxa (xはa以外)のようにスキマがあり、その部分は余分にカウントしている
  • スキマごとに数える
  • スキマの長さをMとすると、そこから取れる「aが存在しない部分文字列」はM * (M+1) / 2 個。これを引く
  • 余分に数えてしまった分を引く。上記例の場合は、'a'について
  • 6(6+1)/2 - 2(2+1)/2

もっと一般的に書くと

f:id:peroon:20190727024127j:plain