ABC-058-C 怪文書 / Dubious Document

■■■問題■■■

すぬけ君は、文字列の書かれた紙から文字をいくつか切り抜いて、
並び替えて別の文字列を作るのが好きです。

明日になると、
すぬけ君は文字列 S1, ・・・ ,Sn のうちどれか1つが書かれた紙がもらえます。
すぬけ君は文字列を作る事をとても楽しみにしているので、
どんな文字列を作るか計画を立てることにしました。 

ただし、すぬけ君はまだどの文字列が書かれた紙がもらえるかを知らないため、
どの文字列が書かれていた場合にも作れる文字列を考えることにしました。

S1, ・・・ ,Sn のどの文字列が書かれていても作れる文字列のうち、
最長のものを求めてください。
最長のものが複数ある場合は、辞書順で最小のものを求めてください。

■■■入力■■■

n
S1
・
・
・
Sn

●1 <= n <= 50
●i=1, ・・・ ,n に対して、 1 <= |Si| <= 50
●i=1, ・・・ ,n に対して、 Si は小文字のアルファベット( a - z )からなる文字列

■■■出力■■■

条件を満たす最長の文字列のうち、辞書順で最小のものを出力せよ。
そのような文字列が空文字列である場合は、空行を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("cbaa");
            WillReturn.Add("daacc");
            WillReturn.Add("acacac");
            //aac
            //cbaa, daacc, acacac のどの文字列からも
            //aa, aac, aca, caa などが作れます。
            //そのうち最も長いものは aac, aca, caa です。
            //この中で辞書順で最小のものは aac なので、
            //aac が答えになります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("a");
            WillReturn.Add("aa");
            WillReturn.Add("b");
            //
            //条件を満たす文字列は空文字列のみです
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] SArr = InputList.Skip(1).ToArray();

        var AnswerDict = new Dictionary<char, int>();
        for (char I = 'a'; I <= 'z'; I++) AnswerDict[I] = int.MaxValue;

        foreach (string EachStr in SArr) {
            var CurrDict = new Dictionary<char, int>();
            for (char I = 'a'; I <= 'z'; I++) CurrDict[I] = 0;

            foreach (char EachChar in EachStr)
                CurrDict[EachChar]++;

            for (char I = 'a'; I <= 'z'; I++) {
                if (CurrDict[I] < AnswerDict[I])
                    AnswerDict[I] = CurrDict[I];
            }
        }

        var sb = new System.Text.StringBuilder();
        for (char I = 'a'; I <= 'z'; I++) {
            if (AnswerDict[I] > 0) {
                for (int J = 1; J <= AnswerDict[I]; J++) {
                    sb.Append(I);
                }
            }
        }
        Console.WriteLine(sb.ToString());
    }
}

解説

文字列ごとに、各文字の個数を集計してます。