PPARTY - Editorial

editorial
, , , ,
1

Contest

Author: Utkarsh Goel

Tester: Rahul Sharma

Editorialist: Rahul Sharma

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Strings, frequency array

PROBLEM:

Given a string S with lowercase Latin letters. Print YES if there exist a letter whose frequency is equal to len(S)/2 otherwise NO

EXPLANATION:

Create a frequency array of size 26 where each index represents each Latin letter and initialize to zero. Now iterate through string S and update count of corresponding letter in frequency array. Finally iterate frequency array and check if frequency at any index is equal to len(S)/2. If such index is found return YES else NO.

COMPLEXITIES:

Time Complexity: O(len(S) + A) for each test case.
Space Complexity: O(A) for each test case.
where A = 26

SOLUTIONS:

Setter's Solution (CPP) 
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    string s;
    cin >> s;
    map<char, int> m;
    int n = s.length();
    if (n % 2 == 1) 
    {
        cout << "NO" << endl;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        m[s[i]]++;
    }
    for (auto r : m)
    {
        if (r.second == n / 2)
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
Setter's Solution (Python) 
def get_dict(s):
    d = dict()
    for c in s:
        if c in d:
            d[c] += 1
        else:
            d[c] = 1
    return d

def solve():
    s = input()
    n = len(s)
    if n % 2 == 1:
        print("NO")
        return
    d = get_dict(s)
    for count in d.values():
        if count == n // 2:
            print("YES")
            return
    print("NO")

t = int(input())
for _ in range(t):
    solve()
2 Likes