文字が部分文字列と同じであり、頻度の差が最大 K である最長の部分列

この問題では、連続する文字が含まれ、すべての文字の頻度の差が K を超えないようなサブシーケンスの最大長を見つけます。

出力を取得するには、指定された文字列の考えられるすべてのサブシーケンスを検索し、その中に各文字が連続して最大の頻度差で含まれているかどうかを確認する必要があります。

問題ステートメント- 小文字のアルファベット文字を含む文字列 alpha が与えられています。さらに、正の整数 K が与えられています。次の規則に従うように、指定された文字列のサブシーケンスの最大長を見つける必要があります。

• 特定の文字はすべて連続して出現する必要があります。

• 文字の頻度の差が K を超えることはできません。

＃＃＃＃＃＃例＃＃＃＃＃＃ ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明 - 「pppqrs」サブシーケンスを取得できます。最大文字頻度は 3 で、最小文字頻度は 1 です。したがって、その差は２となります。そして、すべての文字が連続して含まれます。

＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明 - 「abbbc」サブシーケンスを取得できます。

＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明 - 「nnnnnnn」サブシーケンスを取得できます。

方法1 このメソッドでは、再帰関数を使用して、指定された長さのすべてのサブシーケンスを検索します。さらに、サブシーケンスにすべての文字が連続して含まれているかどうかを確認する関数を定義します。マップ データ構造を使用して、最大および最小の周波数差を計算します。

＃＃＃アルゴリズム＃＃＃

ステップ 1 - 文字の頻度を保存する「f」マッピングを定義します。

ステップ 2 - start が一時文字列の長さに等しく、文字列の長さが 0 より大きい場合は、次の手順に従います。

ステップ 3 - 「minf」変数と「maxf」変数を初期化して、最小周波数と最大周波数を保存します。

ステップ 4 - マップをクリアし、各文字の頻度をマップに保存します。

ステップ 5 - マップ値をループし、周波数の最大値と最小値を見つけます。

ステップ 6 - 最大頻度と最小頻度の差が K 以下の場合は、文字列に連続した文字が含まれているかどうかを確認します。

ステップ 6.1

- checkForContinously() 関数で、特定の文字の最後の位置を保存する「pos」マップを定義します。

ステップ 6.2

- 文字列をトラバースします。現在のキャラクターがマップ内に存在し、キャラクターの現在位置と最後の位置の差が 1 未満の場合は、最後の位置を更新します。それ以外の場合は false を返します。

ステップ 6.3

- キャラクターが存在しない場合は、マップにキャラクターを追加します。

ステップ 6.4

- 最後に true を返します。

ステップ 7

- 文字列に連続した文字が含まれており、頻度の差が K 未満で、「maxi」の値が現在のサブシーケンスの長さより小さい場合は、「maxi」の値を更新します。 '。

ステップ 8

- 現在の文字を除外した後、再帰呼び出しを行います。

ステップ 9

- 現在の文字を一時文字列の末尾に追加します。また、更新された「tmp」文字列を使用して再帰呼び出しを実行します。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 時間計算量 - O(N*2N)。O(N) は連続文字のチェックに使用され、O(2N) はすべてのサブシーケンスの検索に使用されます。

スペースの複雑さ - 一時的なサブシーケンスを保存するには O(N)。 簡単な方法を使用して、指定された文字列のすべてのサブシーケンスを検索します。ただし、これには非常に時間がかかります。大きな文字列の問題を解決するためにこの方法を使用することはお勧めできません。

以上が文字が部分文字列と同じであり、頻度の差が最大 K である最長の部分列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。