# 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"
```