You are not logged in. Please login at www.codechef.com to post your questions!

×

LCH15JAB - Editorial

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:

This question is marked "community wiki".

asked 25 Jan '15, 14:37

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 25 Jan '15, 18:37

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170


include<bits stdc++.h="">

using namespace std;

int main() { int i,t; cin>>t; for(i=0;i<t;i++) {="" <br=""/> 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:;

}

}

link
This answer is marked "community wiki".

answered 19 Dec '18, 00:33

sidbhati's gravatar image

3★sidbhati
0
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,688
×968
×22

question asked: 25 Jan '15, 14:37

question was seen: 2,905 times

last updated: 19 Dec '18, 00:33