Thursday 11 July 2019

Sherlock and Valid String Hacker Rank Solution in C

https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem

Explanation:

ex: aabbcc
then a occurs 2 times
b occurs 2 times and
c occurs 2 times
max of 2,2,2 is 2
min of 2,2,2 is 2

so if max == min then "YES"

ex: aaabbcc

then a occurs 3 times
b occurs 2 times and
c occurs 2 times
max of 3,2,2 is 3
min of 3,2,2 is 2

here max value is 3 and 3 occurred only once

so if max -min == 1 and maxcount == 1 then "YES"

ex: aabbc
then a occurs 2 times
b occurs 2 times and
c occurs 1 times
max of 2,2,1 is 2
min of 2,2,1 is 1
here min value 1 occurred only once
if min == 1 and mincount == 1  then "YES"

BUT

ex: aaabbc
then a occurs 3 times
b occurs 2 times and
c occurs 1 times
max of 3,2,1 is 3
min of 3,2,1 is 1

here min value 1 occurred only once but here answer must be "NO"
 so we need to find second maximum and if second maximum is equal to minimum then the answer is "YES"

so
if min == 1 and mincount == 1  and secondmaximum == min  then "YES"


Program

#include<stdio.h>
#include<limits.h>
int main()
{
    char st[100000];
    scanf("%s",&st);
   
    int smax=0,max=INT_MIN,smin=INT_MAX,min =INT_MAX,i,a[26]={0},c1=0,c2=0;
    for(i=0;st[i]!='\0';i++)
        a[st[i]-'a']++;
   
    for(i=0;i<26;i++)
    {
        if(a[i]!=0)
        {
            if(a[i]==max)
                  c1++;
             else if(a[i]> max)
            {
                 c1=1;
                 smax=max;
                 max=a[i];

               }
              else if (a[i]>smax && a[i]<max)
                     smax=a[i];

             if(a[i]==min)
                  c2++;
              else if(a[i]< min)
             {
                    c2=1;
                    min=a[i];
            }
        }
    }
 
    if(max == min)
        printf("YES");
    else if((max - min == 1 && c1 == 1)|| (min == 1 && c2 == 1&& smax == min))
        printf("YES");
    else
        printf("NO");
}

2 comments:

  1. Replies
    1. explanation of logic to solve the problem is already explained with examples above...in the program i have use the logic to find second maximum...by looking at the if conditions you will be able to understand

      Delete