C++である文字列が別の文字列を「破る」ことができるか判定する方法

問題の概要

同じ長さを持つ2つの文字列 s1 と s2 が与えられたとします。このとき、s1 のある並べ替え(順列)が s2 のある並べ替えを「破る」ことができるか、あるいはその逆が成り立つかどうかを判定する必要があります。

ここで「文字列 a が文字列 b を破る」とは、0 から n-1 までのすべてのインデックス i において x[i] >= y[i](アルファベット順での比較)が常に成立することを意味します。

たとえば、入力が s1 = "abc"、s2 = "xya" の場合、出力は true になります。これは、s2 の並べ替えである "ayx" が、s1 = "abc" の並べ替えである "abc" を破ることができるためです。

解決の手順

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

• check(s1, s2) という関数を定義します。
• i を 0 から s1 のサイズ未満まで1ずつ増やしながらループします。
  • s2[i] < s1[i] であれば false を返します。
• ループを最後まで抜けたら true を返します。
• メイン処理では以下を実行します。
  • s1 を昇順にソートする
  • s2 を昇順にソートする
  • f3 := check(s2, s1) を計算する
  • f4 := check(s1, s2) を計算する
  • f3 または f4 のどちらかが true であれば true を、そうでなければ false を返す

アルゴリズムのポイント

両方の文字列をあらかじめ昇順にソートしておけば、「ある並べ替えが他方を破れるかどうか」は、ソート済みの2つの文字列を先頭から要素ごとに比較し、片方が常に他方以上になっているかを確認するだけで判定できます。計算量はソートに伴い O(n log n) となり、非常に効率的です。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool check(string& s1, string& s2){
        for (int i = 0; i < s1.size(); i++) {
            if (s2[i] < s1[i])
                return false;
        }
        return true;
    }
    bool checkIfCanBreak(string s1, string s2) {
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        bool f3 = check(s2, s1);
        bool f4 = check(s1, s2);
        return f3 || f4;
    }
};
main(){
    Solution ob;
    cout << (ob.checkIfCanBreak("abc", "xya"));
}

入力

"abc", "xya"

出力

1