【C++】各文字を最大1回使用して別の文字列から形成できる文字列の個数を求める方法

この記事では、2つの文字列 str_1 と str_2 が与えられたとき、str_1 の各文字を最大1回ずつ使用することで str_2 を完全に何個形成できるかを求める問題を解説します。つまり、str_1 に含まれる文字を重複して使わずに、str_2 が何回作れるかをカウントするのです。

入力 − str_1 = "technical learning", str_2 = "learning"

出力 − 各文字を最大1回使用して別の文字列から形成できる文字列の数 − 1

説明 − str_2（"learning"）は str_1 の中でちょうど1回形成できます。したがって、カウントは1になります。

入力 − str_1 = "ellohsehelloabcoelhl", str_2 = "hello"

出力 − 各文字を最大1回使用して別の文字列から形成できる文字列の数 − 3

説明 − str_2 は "hello" であるため、str_1 の文字をそれぞれ1回だけ使って "hello" という単語を何回作れるかを調べます。str_1 には3回分の形成が可能なだけの文字が含まれているため、カウントは3になります。

プログラムで使用するアプローチ

• 文字列 str_1 と str_2 を入力として受け取り、それぞれの長さを計算します。その後、さらなる処理のためにこれらのデータを関数へ渡します。

• str_2 が str_1 から何個形成できるかを格納する一時変数 count を宣言し、INT_MAX で初期化します。INT_MAX はC++において変数が保持できる最大値（+2147483647）を表します。

• 英語のアルファベットは26文字であるため、サイズ26の整数型配列を作成し、すべての要素を0で初期化します。

• 0から str_1 の長さまで FOR ループを実行し、arr[str_1[i] - 'a'] に1ずつ加算します。これにより、str_1 に含まれる各文字の出現回数を記録できます。

• 次に、0から str_2 の長さまで FOR ループを実行し、count を「現在の count と arr[str_2[i] - 'a'] のうち小さい方」で更新します。

• count を返します。

• 結果を出力します。

このアプローチのポイントは、「形成可能な個数は、str_2 に必要な文字の中で最も出現回数の少ない文字によって制限される」という点です。そのため、各文字の出現回数を数えたうえで最小値を取れば、それがそのまま答えになります。

例

#include <bits/stdc++.h>
using namespace std;
int atmost_once(string str_1, int len_str1, string str_2, int len_str2){
    int count = INT_MAX;
    int arr[26] = { 0 };
    for (int i = 0; i < len_str1 ; i++){
       arr[str_1[i] - 'a'] += 1;
    }
    for (int i = 0; i < len_str2; i++){
       count = min(count, arr[str_2[i] - 'a']);
    }
    return count;
}
int main(){
    string str_1 = "technical learning";
    int length_str1 = str_1.length();
    string str_2 = "learning";
    int length_str2 = str_2.length();
    cout<<"Count of strings that can be formed from another string using each character at-most
once are: "<<atmost_once(str_1,length_str1, str_2, length_str2);
    return 0;
}

出力

上記のコードを実行すると、以下のような出力が得られます −

Count of strings that can be formed from another string using each character at-most once are: 1