LCH15JAB - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Roman Rubanenko
Editorialist: Paweł Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Ad-hoc

PROBLEM:

As the name suggest, this problem is really easy. You are given a string S. The task is to decide whether there exists a character for which a number of occurrences of this character in S is equal to a sum of occurrences of all other characters in S.

QUICK EXPLANATION:

Count a number of occurrences for each of 26 possible letters and for each such letter, check if the counter equals a sum of occurrences of all other characters in S.

EXPLANATION:

First observation:
There are at most 26 possible distinct letters in S because the Latin alphabet has 26 letters (‘a’ to ‘z’).

Let cnt[a] denote number of occurrences of letter ch in S. We can compute the cnt table iterating over S from left to right and maintaining and updating a counter for each character.

int cnt[26];
for (i = 0; i < 26; i++)
    cnt[i] = 0;
for (i = 0; i < s.size(); i++)
    cnt[s[i] - 'a']++;

Let n be the length of S. A simple observation which may help is that a sum of occurrences of all characters different than ch equals n - cnt[ch].

Based on this fact we can decide out problem easily. Just iterate over all possible letters and check if there is a letter ch for which cnt[ch] = n - cnt[ch]

Also note that if you are an C++/Java user, you can also make use of map/Map in STL(Standard Template Library)/ Java Collections. map/Map is a balanced red black tree, in which you can put (key, value) pairs and also search for value corresponding to the key. All these operations are logarithmic in number of elements present in the data structure. So you can use map/Map to count number of occurrences of a particular character too. For more faster solution, you can use unordered_map/HashMap too which is implemented using hashing and gives constant time for the above operations.

TIME COMPLEXITY

For a solution which uses counters is O(n) and the same for a solution using map/Map or unordered_map/HashMap, because if you use it, you will store up to 26 entries in it, so this is not much an upgrade. I suggest to use a simple table because for such small dataset it is the fastest method.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

2

#include<bits/stdc++.h>
using namespace std;

int main()
{
int i,t;
cin>>t;
for(i=0;i<t;i++)
{
string s;
int count=0;
int j,k;
cin>>s;

	for(j=0;j<s.length();j++)
	{
		count=0;
		for(k=j;k<s.length();k++)
		{
			if(s[j]==s[k])
			{
				count++;
			}
		}
		if(s.length()%2!=0)
		{
			cout<<"NO\n";
			goto end;
		}
		if(count==(s.length()/2))
		{
			cout<<"YES\n";
			goto end;
		}
	}
	
	cout<<"NO\n";
	end:;
	
}

}