我们要在字符串中出现子串 "abcdefghijklmnopqrstuvwxyz"(长度为 26,下文记为目标串 T),允许的操作是:选择一个下标把字符改成任意小写字母。问最少需要多少次操作;若无法做到输出 -1。
关键事实
n < 26,无论如何修改都不可能出现长度为 26 的子串,答案为 -1。n ≥ 26,一定可以:选择任意长度为 26 的窗口,把其中的字符逐个改成 T 对应位置即可。因此答案等于
所有长度为 26 的窗口与 T 的最小“汉明距离”(不相等字符的个数)。给定一个长度为 n 的字符串 s,字符串仅由小写字母组成,下标从 1 开始。你可以对字符串执行以下操作任意次:
请问最少需要多少次操作,才能让字符串中出现子串"abcdefghijklmnopqrstuvwxyz"。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册