Saturday, 28 January 2017

Sherlock And Valid String

You know my powers, my dear Watson, and yet at the end of three months I was forced to confess that I had at last met an antagonist who was my intellectual equal.
A "valid" string is a string  such that for all distinct characters in  each such character occurs the same number of times in .
For example, aabb is a valid string because the frequency of both characters a and b is , whereas aabbc is not a valid string because the frequency of characters ab, and c is not the same.
Watson gives a string  to Sherlock and asks him to remove some characters from the string such that the new string is a "valid" string.
Sherlock wants to know from you if it's possible to be done with less than or equal to one removal.
Input Format
The first and only line contains , the string Watson gives to Sherlock.
Constraints
  • String  contains lowercase letters only ().
Output Format
Output YES if string  can be converted to a "valid" string by removing less than or equal to one character. 
Else, output NO.
Sample Input
aabbcd
Sample Output
NO
Explanation
 is the minimum number of removals required to make it a valid string. It can be done in following two ways:
Remove c and d to get aabb
Or remove a and b to get abcd.
Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int main() 
{
 char string[100000],set[26];
 cin>>string;
 long long length=strlen(string);
 memset(set,0,sizeof(set));
 for(long long int i=0;i<length;i++)
 {
  set[string[i]-'a']++;
 }

 long long maxFreq=0,nonzero = 0,freq=0,temp;
 for(long long i=0;i<26;i++)
 {
  temp = 0;    //equal non zeroes
  if(set[i]) 
  {
   nonzero++;    //non zeroes
  }
  for(int j=0;j<26;j++)
  {
   if(set[i]==set[j]&&set[i]&&set[j]) 
   temp++;               //incrementing equal nonzeroes
  }
  if(temp > maxFreq)
  {
   maxFreq = temp;
   freq = set[i];          //setting current frequency
  }
 }
 if(maxFreq == nonzero)         //maxfrequency of non zeroes
 {
  cout<<"YES\n";
 }
 else 
 {
  if(maxFreq == nonzero-1)
  {
   short flag=-1;
   for(int i=0;i<26;i++)
   {
    if(set[i]!=freq && set[i] && (abs(freq-set[i]) == 1||set[i]==1))
    {
     flag++;
    }
   }
   if(!flag)
    cout<<"YES\n";
   else
    cout<<"NO\n";
  }
  else cout<<"NO\n";
 }
 return 0;




Share:

0 comments:

Post a Comment