プロフィール
AtCoder PR

【AtCoder ABC082B Typescript】問題解説「B – Two Anagrams」

 
記事内に商品プロモーションを含む場合があります
Contents
  1. 問題の概要
  2. 辞書順の定義
  3. ポイント
  4. よくある間違い：.join() と join("") の違い
  5. 文字列ソートの基本パターン
  6. 辞書順比較をシンプルに書く
  7. TypeScript 実装例
  8. テスト例
  9. まとめ

問題の概要

AtoCoderのページ：https://atcoder.jp/contests/abc082/tasks/abc082_b

  1. 英小文字のみからなる文字列s, tが与えられる。
  2. sの文字を任意の順序に並べ替えてs′を作成し、同様にtを任意の順序に並べ替えてt′を作成する。
  3. そのとき、辞書順でs′<t′となる並べ替えが存在するかを判定する。
  4. 判定結果が真であれば “Yes”、そうでなければ “No” を出力する。
  5. 文字列長は1以上100以下。英小文字のみ。

この問題のポイントは、どの並べ替えを試せばよいかを考える部分です。全パターンを試すのは計算量的に非現実的なので、「sをできるだけ小さく、tをできるだけ大きく並べ替える」という極端な組み合わせで比較すればよい、という発想になります。

辞書順の定義

  • 文字列a, bを比較するとき、英小文字の場合は先頭から順に文字を比較し、最初に異なる位置iがあれば、a_i < b_i なら a<b、a_i > b_i ならa>bと判定する。
  • 全部一致した場合は長さ比較により、短い方が小さいとみなす。
  • 例: “xy” < “xya”。“atcoder” < “atlas”。
  • 先頭文字が異なれば、次の文字以下は無視して先頭だけで大小が決まる。

並べ替えたs′とt′も同じ定義に従って比較します。

ポイント

TypeScript/JavaScript で「文字列の文字を並べ替えて辞書順比較を行う」ような処理を書くとき、つい見落としがちな点や、よりシンプルに書くためのポイントがあります。本記事では、以下のような例をもとに、よくある間違いや改善方法、最終的にそのまま使えるコードサンプルをご紹介します。

  • よくある間違い例: split("").sort().join() と書いてしまい、期待した文字列連結ができていない
  • 比較ロジックの簡略化: 逐次ループで文字を比較するより、文字列同士の < 演算子を活用する

よくある間違い：.join() と join("") の違い

文字列をソートするためにまず文字列を配列化し、.sort() を呼び、その後に .join() で再び文字列に戻す、という流れはよく使われます。しかし、join() を引数なしで呼ぶと、配列要素の間にカンマが入ります。

const arr = ['a', 'b', 'c'];
console.log(arr.join());   // "a,b,c"
console.log(arr.join("")); // "abc"

ソート後に "abc" のように連結したい場合は、必ず join("") と書く必要があります。

function sortStringAsc(s: string): string {
  return s.split("").sort().join("");  // 正: 空文字で連結
}
// NG: join() のままだと "a,b,c" になる

まずここを間違うと、後続の辞書順比較などがすべて意図した結果と異なる出力になります。

文字列ソートの基本パターン

TypeScript/JavaScript で文字列の各文字を昇順・降順に並べ替える方法は以下の通りです。

昇順ソート（アルファベット順）

英小文字のみの文字列であれば、UTF-16 コード順がそのままアルファベット順になるため、比較関数なしの .sort() で十分です。

function sortStringAsc(s: string): string {
  return s.split("").sort().join("");
}

  • split("") で1文字ずつの配列にし、
  • sort() で昇順にソートし、
  • join("") で文字列に戻します。

降順ソート

降順にしたい場合は比較関数を渡します。英小文字のみを対象とするなら、charCodeAt の差分でもよいですが、汎用的には localeCompare を使ってもOKです。

// charCodeAt を使う例
function sortStringDesc(s: string): string {
  return s
    .split("")
    .sort((a, b) => b.charCodeAt(0) - a.charCodeAt(0))
    .join("");
}

// localeCompare を使う例
function sortStringDescLocale(s: string): string {
  return s
    .split("")
    .sort((a, b) => b.localeCompare(a))
    .join("");
}

どちらでも機能します。英小文字のみなら前者で十分高速です。

辞書順比較をシンプルに書く

「並べ替えた文字列 s′ と t′ の辞書順比較を行い、s′ < t′ かどうかを判定する」という目的がある場合、TypeScript/JavaScript の < 演算子を使えば、自前で文字ごとにループする必要はありません。

if (convertedS < convertedT) {
  console.log("Yes");
} else {
  console.log("No");
}

  • < や >、<=、>= を文字列に適用すると、ECMAScript 標準の辞書順（コードポイント順＋長さによる判定）で比較されます。
  • 先頭の文字が違えばそこだけで大小が決まり、先頭が同じ場合は次の文字以降を比較し、完全に一致した場合は長さで短い方が小さいと判定されます。
  • すなわち、アルファベットの文字列比較でも標準比較で十分です。

手書きで文字ごとに charCodeAt を比較する実装は、先頭一致ケースや長さ差、エッジケース処理などを自前で実装する必要がありミスしやすいため、標準の < 比較を使うほうが安全で簡潔です。

TypeScript 実装例

以下は Node.js 環境で fs.readFileSync("/dev/stdin", "utf8") から入力を受け取り、判定結果を出力するコード例です。

import * as fs from "fs";

function sortStringAsc(s: string): string {
	return s
	.split("")
	.sort()
	.join("");
}

function sortStringDesc(s: string): string {
	return s
	.split("")
	.sort((a, b) => {
		return b.charCodeAt(0) - a.charCodeAt(0);
	})
	.join("");
}

// エントリポイント　inputに入力データ全体が入る
function Main(input: string) {
	const [strS, strT] = input.trim().split('\n');
	
	const convertedS = sortStringAsc(strS);
	const convertedT = sortStringDesc(strT);

	if(convertedS < convertedT){
		console.log("Yes");
	} else {
		console.log("No");
	}
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
const inputData: string = fs.readFileSync("/dev/stdin", "utf8")
Main(inputData);

ポイント解説

  • ソート関数
    • join("") を忘れずに。join() だけだとカンマ区切り文字列になる点に注意。
    • 降順は b.charCodeAt(0) - a.charCodeAt(0) や b.localeCompare(a) など好みで。
  • 比較
    • convertedS < convertedT のみで判定。
    • convertedS === convertedT の場合も convertedS < convertedT が false になるので自動的に “No” になる。元文字列が同じ並びの multiset であっても、この比較だけで適切に扱える。
  • 不要チェックの排除
    • 元の strS === strT を先にチェックして “No” とする必要は基本的にありません。ソート後に同一であれば自動的に “No” になるため、コードをシンプルに保てます。

テスト例

いくつか手元で動作確認するときの例です。Node.js でファイルに上記コードを保存し、標準入力を渡して試してください。

  1. s="yx", t="axy"
    • convertedS="xy", convertedT="yx a" のような誤りがないか注意（join(“”) が重要）
    • 正しくは sortDesc("axy") → "yx a" ではなく "yx a" ではなく "yx a" という誤り例ではなく、実際は ["a","x","y"].sort(desc) → ["y","x","a"] → "yxa". 比較は "xy" < "yxa" → Yes。
  2. multiset が同じ例: s="ab", t="ba"
    • convertedS="ab", convertedT="ba" → "ab" < "ba" → Yes
    • 元文字列は異なるが multiset 同じ場合でも結果は適切に Yes/No を返す。
  3. 同一並び例: s="abc", t="cba"
    • convertedS="abc", convertedT="cba" → "abc" < "cba" → Yes
  4. 比較で No になる例: s="cba", t="abc"
    • convertedS="abc", convertedT="cba" → "abc" < "cba" → Yes, ただし文脈によっては意味が異なる問題設定もあるので要件を確認。
    • ここで示したロジックは「s を最小化、t を最大化して比較する」という典型的アプローチに沿ったもの。

まとめ

  • 文字列を並べ替えるときは、必ず split("").sort().join("")（昇順）や比較関数付き join("")（降順）と書く。join() のままにしない。
  • 並べ替え後の辞書順比較は自前のループよりも文字列同士の < 演算子を使えばシンプルで確実。
  • 元文字列同士の等値チェックをわざわざ行う必要はなく、ソート後に等しければ < 比較が false になるだけで問題なし。
  • 入力処理は split(/\r?\n/) で改行を吸収し、最低限のチェックを入れておくと安心。
  • 競技プログラミングや小規模ユーティリティであれば、この形をそのままコピー＆ペーストで活用できる。

これらのポイントを意識すれば、文字列ソート→辞書順比較のコードはバグを減らしつつ短く書けます。

RELATED POST