JavaScriptで各文字を1回だけ出現させ、辞書順最小の文字列を作る方法

本記事では、JavaScriptを使って「各文字が1回だけ出現する文字列」を作成する問題を解説します。単に重複を取り除くだけでなく、結果として得られる文字列が辞書順で最小になるよう、残す文字の出現位置を適切に選ぶ必要があります。

問題の概要

文字列 str を唯一の引数として受け取るJavaScript関数を作成してください。

この関数は、入力文字列をもとに新しい文字列を生成します。生成される文字列では、それぞれの文字が1回だけ出現し、かつ残した文字の組み合わせが辞書順で最小になるようにします。

例えば、関数への入力が次の場合：

const str = 'cbacdcbc';

期待される出力は次のとおりです。

const output = 'acdb';

出力の解説

この文字列には 'c' が4回登場していますが、どの出現位置を残してもよいわけではありません。適切な位置の 'c' を削除することで、結果の文字列は辞書順で最も小さくなります。'a' や 'b' についても同様に、残す位置を選ぶことで最小の並びを実現しています。

サンプルコード

この問題を解くコードは以下のとおりです。

const str = 'cbacdcbc';
const removeDuplicates = (str = '') => {
   if (str.length <= 1) {
      return str;
   };
   let flag;
   let string = "";
   let legend = new Array(26).fill(-1);
   let last = "z";
   let ind = 0;
   for (let i = str.length - 1; i > -1; i--) {
      const element = str[i];
      if (legend[element.charCodeAt() - 97] < 0) {
         legend[element.charCodeAt() - 97] = i;
         last = element;
         ind = i;
         string += element;
      } else {
         if (last >= element) {
            last = element;
            ind = i;
         }
      }
   }
   let finalStr = last;
   while (string.length > finalStr.length) {
      legend.fill(-1);
      for (let i = str.length - 1; i > ind; i--) {
         const element = str[i];
         if (finalStr.indexOf(element) < 0) {
            if (legend[element.charCodeAt() - 97] < 0) {
               legend[element.charCodeAt() - 97] = i;
               last = element;
               flag = i;
            } else {
               if (last >= element) {
                  last = element;
                  flag = i;
               }
            }
         }
      }
      ind = flag;
      finalStr += last;
   }
   return finalStr;
};
console.log(removeDuplicates(str));

コードの解説

このアプローチの基本的な考え方は以下の3点です。

• 全体の走査：まず文字列全体を調べて、使用されている文字の種類を把握し、すべての文字を含む部分文字列の中で最小の先頭文字を持つものを見つけます。
• 右から左へのループ：ループを右から左に向かって実行することで、部分文字列の開始位置と先頭の最小文字を記憶しながら処理でき、ロジックが理解しやすくなります。
• 確定済み文字の除外：次に、先頭の最小文字を除いた範囲に対して再度右から左へループを行いますが、このときすでに結果に採用した文字は無視します。これを必要な文字数分だけ繰り返します。

実行結果

コンソールへの出力は次のようになります。

acdb