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

View as PDF



Author:
Problem type
Points: 100 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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
d

Comments


  • 1
    PhanHuyKhang    9:16 a.m. 29 oct, 2020 edit 2

    e lộn ạ


    • 8
      SPyofgame    6:45 p.m. 10 jun, 2020 edited

      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;
      }
      
      1 reply