Pythonで作る強力なパスワードチェッカー:最小変更回数を求めるアルゴリズム

強力なパスワードの条件とは?

文字列としてパスワードが与えられたとき、そのパスワードを「強力なパスワード」にするために必要な最小の変更回数を求める問題を考えてみましょう。強力なパスワードとみなされるには、以下の条件をすべて満たす必要があります。

• 長さは6文字以上20文字以内であること
• 小文字を少なくとも1つ、大文字を少なくとも1つ、数字を少なくとも1つ含むこと
• 同じ文字が3つ以上連続してはならない(例:「aaa」「PPP」「888」など)

たとえば入力が "aa26bbb" の場合、必要な変更は1回です。このパスワードには大文字が含まれておらず、さらに「b」が3つ連続しているため、どれか1つの「b」を大文字に置き換えれば、両方の問題を同時に解決できるからです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

1. missing_type を 3 に初期化します。これは「不足している文字種の数」を表します。
2. 小文字が1つでも含まれていれば missing_type を1減らします。
3. 大文字が1つでも含まれていれば missing_type を1減らします。
4. 数字が1つでも含まれていれば missing_type を1減らします。
5. change = 0、one = 0、two = 0、p = 2 として初期化します。
6. p が文字列の長さ未満である間、次の処理を繰り返します。
   • s[p] が s[p-1] および s[p-2] と同じ場合(3連続が発生している場合):
     • length を2に設定し、s[p] が s[p-1] と等しい限り length を増やしながら p を進めます。
     • change に length / 3 を加算します。
     • length が3で割り切れる場合は one を1増やし、3で割って1余る場合は two を1増やします。
   • それ以外の場合は p を1増やします。
7. 文字列の長さが6未満の場合:max(missing_type, 6 - 長さ) を返します。
8. 文字列の長さが20以下の場合:max(missing_type, change) を返します。
9. それ以外(長さが20超)の場合:
   • delete = 文字列の長さ - 20 とします。
   • change から min(delete, one) を引きます。
   • change から min(max(delete - one, 0), two * 2) / 2 を引きます。
   • change から max(delete - one - 2 * two, 0) / 3 を引きます。
10. 最後に delete + max(missing_type, change) を返します。

ここでのポイントは、連続文字の長さを3で割った余りによって、削除操作で置換操作を何回節約できるかが変わる点です。余りが0の場合は1回の削除で済み(one)、余りが1の場合は2回の削除が必要(two)、余りが2の場合は削除による節約ができません。この性質を利用して、文字列が長すぎる場合の削除回数を効率的に計算しています。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def strongPasswordChecker(self, s):
        missing_type = 3
        if any('a' <= c <= 'z' for c in s): missing_type -= 1
        if any('A' <= c <= 'Z' for c in s): missing_type -= 1
        if any(c.isdigit() for c in s): missing_type -= 1
        change = 0
        one = two = 0
        p = 2
        while p < len(s):
            if s[p] == s[p-1] == s[p-2]:
                length = 2
                while p < len(s) and s[p] == s[p-1]:
                    length += 1
                    p += 1
                change += length / 3
                if length % 3 == 0: one += 1
                elif length % 3 == 1: two += 1
            else:
                p += 1
        if len(s) < 6:
            return max(missing_type, 6 - len(s))
        elif len(s) <= 20:
            return max(missing_type, change)
        else:
            delete = len(s) - 20
            change -= min(delete, one)
            change -= min(max(delete - one, 0), two * 2) / 2
            change -= max(delete - one - 2 * two, 0) / 3
            return delete + max(missing_type, change)

ob = Solution()
print(ob.strongPasswordChecker('aa26bbb'))

入力

"aa26bbb"

出力

1

まとめ

このアルゴリズムは、文字種の不足・短すぎる長さ・長すぎる長さ・連続文字という4つの観点から必要な操作回数を評価し、それぞれのケースで最適な操作(追加・置換・削除)を選択することで最小変更回数を導きます。計算量は文字列を一度走査するだけなので O(n) と非常に効率的です。パスワードポリシーのバリデーション機能を実装したい場合などに、応用価値の高いアルゴリズムといえるでしょう。