問題
英小文字からなる文字列 が与えられる。
に最も多く出現する文字を求めよ。
ただし、そのような文字が複数ある場合は、そのうちアルファベット順で最も早いものを答えよ。
入力
1行に、文字列 が与えられる。
条件
- 実行時間制限: 2s
- メモリ制限: 1024MB
の各文字は英小文字である。
出力
に最も多く出現する文字のうち、アルファベット順で最も早いものを1行で出力すること。
解法
文字列 の各文字について順番に見ていき、
a から z までの文字がそれぞれ何回出現したのかを数えていくことがまずは必要です。
この数え方の管理方法としては、アルファベットは全部で26文字であることから、 cnt[26] のような26個分の配列を用意しておき、「 a からいくつ離れているもののカウントを1つ増やす」という方法で行うことができます。
例えば C++ では、文字 s[i] のカウントを1つ増やしたいときについては、 cnt[s[i] - 'a']++; によってこの操作が可能になります。
以上によって得られた cnt[26] に対して、順番に値を見ていき、そのうち最大かつ出現が最も早いものを出力すれば、この問題の答えが得られます。
この方法は の計算量で答えが得られるので、実行時間制限にも十分間に合うと言えます。
ソースコード
main() 関数の中に、答えを出力する部分を直接実装しました。
string s; int m = 0, cnt[26]; // m は cnt[i] の最大値を表す int main() { // 値の入力 cin >> s; // s の各文字について見ていき、 cnt の値を更新していく for (int i = 0; i < s.length(); i++) { cnt[s[i] - 'a']++; } char ans; // 答えとなる文字を表す ans // i = 0, ..., 25 の順に、cnt[i] の値を見ていく for (int i = 0; i < 26; i++) { if (m < cnt[i]) { // m が cnt[i] より小さいとき、 m と ans を更新する m = cnt[i]; ans = 'a' + i; } } cout << ans << endl; return 0; }
