Hackerrank - Sherlock and the Valid String Solution

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just  character at  index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.

For example, if , it is a valid string because frequencies are . So is  because we can remove one  and have  of each character in the remaining string. If  however, the string is not valid as we can only remove  occurrence of . That would leave character frequencies of .

Function Description

Complete the isValid function in the editor below. It should return either the string YES or the string NO.

isValid has the following parameter(s):

• s: a string

Input Format

A single string .

Constraints

• Each character

Output Format

Print YES if string  is valid, otherwise, print NO.

Sample Input 0

aabbcd

Sample Output 0

NO

Explanation 0

Given , we would need to remove two characters, both c and d  aabb or a and b  abcd, to make it valid. We are limited to removing only one character, so  is invalid.

Sample Input 1

aabbccddeefghi

Sample Output 1

NO

Explanation 1

Frequency counts for the letters are as follows:

{'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 2, 'f': 1, 'g': 1, 'h': 1, 'i': 1}

There are two ways to make the valid string:

• Remove  characters with a frequency of : .
• Remove  characters of frequency : .

Neither of these is an option.

Sample Input 2

abcdefghhgfedecba

Sample Output 2

YES

Explanation 2

All characters occur twice except for  which occurs  times. We can delete one instance of  to have a valid string.

Solution in Python

from collections import Counter

def isValid(s):
    d = Counter(Counter(s).values())
    if len(c)==1:
        return "YES"
    if len(c)>2:
        return "NO"
    if 1 in c.values() and (c[min(c.keys())]==1 or (max(c.keys()) - min(c.keys())==1)):
        return "YES"
    else:
        return "NO"

print(isValid(input()))

For full detailed answer explanation

Since we have to make the count of each letter equal first we will count the occurrence of each letter using Counter.

Let s = "abcdefghhgfedecba"

>>> Counter(s)
Counter({'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 3, 'f': 2, 'g': 2, 'h': 2})
>>> Counter(s).values()
dict_values([2, 2, 2, 2, 3, 2, 2, 2])

The following gives us count of each frequency

>>> Counter(Counter(s).values())
Counter({2: 7, 3: 1})

Now we know that there are 7 letters that occur equal number of times(2) and 1 letter that occur 3 times

Condition 1

Our string is already valid if all items already have  the same Count.

That is len(Counter(Counter(s).values()))==1

Example

>>> s = "abcdfghhgfedecba"
>>> Counter(s)
Counter({'a': 2, 'b': 2, 'c': 2, 'd': 2, 'f': 2, 'g': 2, 'h': 2, 'e': 2})
>>> Counter(s).values()
dict_values([2, 2, 2, 2, 2, 2, 2, 2])
>>> Counter(Counter(s).values())
Counter({2: 8})
>>> len(Counter(Counter(s).values()))
1

if len(c)==1:
    return "YES"

Condition 2

Our string will never be valid if we have more than 2 different type of frequencies of letters

Example

>>> s = "aabbbcccc"
>>> Counter(s)
Counter({'a': 2, 'b': 3, 'c': 4})
>>> Counter(s).values()
dict_values([2, 3, 4])
>>> Counter(Counter(s).values())
Counter({2: 1, 3: 1, 4: 1})
>>> len(Counter(Counter(s).values()))
3

if len(c)>2:
    return "NO"

Condition 3

We can make our string valid if our string has only 2 type of frequencies of letters and has the following conditions

• The difference between the most common frequency and the other frequency is 1.

Example when s = "aabbccddd", our most common frequency is 2 since most of our letters appear 2 times. And the uncommon frequency is 3. Now we can remove one letter(d) from the frequency 3 to make all letters appear twice.

• Another important condition for above case is that our uncommon frequency appears only once.

Example when s = "aabbccde", our most common frequency is 2 since most of our letters appear 2 times. And the uncommon frequency is 1. Now we can remove one letter(d or e), but we will still be left with uneven frequency.

• The uncommon frequency is 1

Example when s = "aaabbbcccd", our most common frequency is 3 since most of our letters appear 3 times. And the uncommon frequency is 1. Now we can remove the letter(d) to make all letters appear 3 times.

We can write the above condition as follows

if 1 in c.values() and (c[min(c.keys())]==1 or (max(c.keys()) - min(c.keys())==1)):
    return "YES"
else:
    return "NO"