 # PPARTY - Editorial

Contest

Author: Utkarsh Goel

Tester: Rahul Sharma

Editorialist: Rahul Sharma

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