コードを書き終えると、面接官はほぼ必ず「時間計算量と空間計算量は?」と聞きます。時間は最悪の場合で、空間は解法が確保する追加のメモリで答え、それぞれの原因になっている行を示してください。
最も内側の処理が何回実行されるかを数えてください。和n + (n - 1) + ... + 1は約n^2 / 2なので、入力に対する二重の入れ子ループは、内側のループがi + 1から始まる場合でもO(n^2)です。ソートはO(n log n)で、通常はその後の線形走査より支配的です。ハッシュセットの検索は平均O(1)ですが、集合そのものはO(n)の空間を使います。
隠れたコストに注意してください。JavaやJavaScriptでは、ループ内で+を使って文字列を組み立てると、毎回それまでに作ったものをすべてコピーします。リストをスライスするとコピーが作られます。各ステップで残りが半分になるので、百万個の要素に対する二分探索は約20ステップで済みます。