Tìm ký tự (THT TP 2015)

Tác giả:

Dạng bài

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nhập vào từ bàn phím một xâu kí tự \(S\). Hãy viết ra một kí tự có số lần xuất hiện nhiều nhất trong xâu \(S\) (có phân biệt kí tự hoa và kí tự thường).

Lưu ý: Nếu có nhiều kí tự có cùng số lần xuất hiện nhiều nhất trong xâu \(S\) thì in ra kí tự xếp theo thứ tự từ điển nhỏ nhất trong xâu đó.

Input

Dòng đầu tiên và duy nhất chứa 1 xâu \(S\) (chỉ gồm các chữ cái trong tập \(\{a,\dots,z, A,\dots,Z\}\)) \((|S| \leq 10^6)\)

Output

In ra kí tự xuất hiện nhiều nhất trong xâu \(S\).

Example

Test 1

Input

abcdaadDedgdAAA

Output

Bình luận

`Spoiler Alert`

Hint 1

Với mỗi kí tự, tìm số lần xuất hiện của nó trong xâu

Reference AC code | O(n * 26 * 2) time | O(n) auxiliary space | String

C++

/// Nhan xau
string s;
cin >> s;
int n = s.size();

/// Tim tan so
char resc = 'A'; int freq = 0; 
for (char c = 'a', C = 'A'; c <= 'z' && C <= 'Z'; ++c, ++C)
{
    int lower_freq = 0; /// lowercase latin case
    int upper_freq = 0; /// uppercase latin case

    for (int i = 0; i < n; ++i)
        lower_freq += (s[i] == c),
        upper_freq += (s[i] == C);

    if (upper_freq > freq) resc = C, freq = upper_freq; /// priority so thu tu tu dien nho hon
    if (lower_freq > freq) resc = c, freq = lower_freq;
}

cout << resc;

Hint 2

Với mỗi kí tự trong xâu, tăng tần số của nó

Tìm kí tự nhỏ nhất có tần số xuất hiện lớn nhất

Reference AC code | O(n) time | O(n) auxiliary space | STL

C++

int main()
{
    string s;
    getString(s);

    vector<int> freq(256, 0);
    for (char c : s) freq[c]++;

    int mx = *max_element(freq.begin(), freq.end()); /// tim tan so lon nhat
    for (int i = 0; i < 256; ++i)
        if (freq[i] == mx)
            return cout << char(i), 0;

    return 0;
}

Reference AC code | O(n log n) time | O(n) auxiliary space | STL

C++

int main()
{
    /// input
    string s;
    cin >> s;

    /// solve
    int mx = 0; /// maximum frequency
    map<char, int> M;
    for (char c : s) mx = max(mx, ++M[c]);

    /// find result
    for (pair<char, int> e : M)
        if (e.second == mx)
            return cout << e.first, 0;        

    return 0;
}

Hint 3

Bạn cũng có thể giải trực tiếp

Reference AC code | O(n) time | O(1) auxiliary space | Online solving

C++

inline bool isLatin(char c) { return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z'); }
int main()
{
    char resc = 'A'; int mx = 0;
    vector<int> freq(256, 0);
    for (char c; isLatin(c = getchar()); )
    {
        freq[c]++;
        if (mx == freq[c]) { resc = min(resc, c); continue; }
        if (mx <  freq[c]) { resc = c; mx = freq[c];        }
    }

    cout << resc;
    return 0;
}

4

vinhntndu 7:21 p.m. 10 Tháng 6, 2020

viết sol kinh zị

2 bình luận nữa