# HackerRank Sherlock and the Valid String Solution

Hello Programmers, In this post, you will learn how to solve HackerRank Sherlock and the Valid String Solution. This problem is a part of the HackerRank Algorithms Series.

One more thing to add, don’t straight away look for the solutions, first try to solve the problems by yourself. If you find any difficulty after trying several times, then look for the solutions. We are going to solve the HackerRank Algorithms problems using C, CPP, JAVA, PYTHON, JavaScript & SCALA Programming Languages.

## 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 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string s, determine if it is valid. If so, return `YES`, otherwise return `NO`.

Example

s = abc

This is a valid string because frequencies are {a : 1, b : 1, c : 1}.

s = abcc

This is a valid string because we can remove one c and have 1 of each character in the remaining string.

s = abccc

This string is not valid as we can only remove 1 occurrence of c. That leaves character frequencies of {a : 1, b : 1, c : 2}.

Function Description

Complete the isValid function in the editor below.

isValid has the following parameter(s):

• string s: a string

Returns

• string: either `YES` or `NO`

Input Format

A single string s.

Constraints

• 1 <= |s| <= 105
• Each character s[i] ∈ ascii[a – z]

Sample Input 0

```aabbcd
```

Sample Output 0

```NO
```

Explanation 0

Given s = “aabbcd”, 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 s 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 4 characters with a frequency of 1{fghi}.
• Remove 5 characters of frequency 2{abcde}.

Sample Input 2

```abcdefghhgfedecba
```

Sample Output 2

```YES
```

Explanation 2

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

## HackerRank Sherlock and the Valid String Solution

### HackerRank Sherlock and the Valid String Solution in C

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int fre[26];
int main() {

char S[100001];
scanf("%s",&S);
int len=strlen(S);
int i=0;
for(i=0;i<len;i++)
{
fre[S[i]-'a']++;
}
int flag=0;
int same=0;
int count=0;
for(i=0;i<26;i++)
{
if(flag==0&&fre[i]!=0)
{
flag=1;
same=fre[i];
}
if(flag==1&&fre[i]!=0&&fre[i]!=same)
{
count++;
}

}
if(count<=1)
printf("YES");
else
printf("NO");
return 0;
}```

### HackerRank Sherlock and the Valid String Solution in Cpp

```#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

int main() {
string S;
while(cin >> S) {
int cnt[26]={};
rep(i, S.size()) ++ cnt[S[i] - 'a'];
bool ans = false;
rep(b, 27) {
vi v;
rep(a, 26) if(cnt[a] - (a == b) != 0)
v.push_back(cnt[a] - (a == b));
ans |= v.empty() || count(all(v), v[0]) == v.size();
}
puts(ans ? "YES" : "NO");
}
return 0;
}```

### HackerRank Sherlock and the Valid String Solution in Java

```import java.io.*;
import java.util.*;

public class _101HackJuneqA {

public static void main(String args[]) {
PrintWriter w = new PrintWriter(System.out);

int c[] = new int[26];

for(int i=0;i<s.length;i++){
if(s[i] >= 'a' && s[i] <= 'z')
c[s[i]-'a']++;
}

boolean yes = false;

int ans = 0;
for(int j=0;j<26;j++){
if(c[j] != 0){
if(ans == 0)
ans = c[j];
else if(ans != c[j]){
ans = -1;
break;
}
}
}

if(ans != -1)
yes = true;

for(int i=0;i<s.length;i++){
c[s[i]-'a']--;
int ans1 = 0;

for(int j=0;j<26;j++){
if(c[j] != 0){
if(ans1 == 0)
ans1 = c[j];
else{
if(c[j] != ans1){
ans1 = -1;
break;
}
}
}
}

c[s[i]-'a']++;
if(ans1 != -1)
yes = true;
}

w.println(yes ? "YES" : "NO");
w.close();
}

private InputStream stream;
private byte[] buf = new byte[8192];
private int curChar;
private int snumChars;
private SpaceCharFilter filter;

this.stream = stream;
}

public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

int res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

int c = snext();
while (isSpaceChar(c))
c = snext();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}```

### HackerRank Sherlock and the Valid String Solution in Python

```# Enter your code here. Read input from STDIN. Print output to STDOUT
s = str(raw_input())
d = {}
for c in s:
if c in d:
d[c]+=1
else:
d[c]=1
k = sorted(d.values())
if len(k) == 1:
print "YES"
elif k[0] == 1 and k[1] == k[-1]:
print "YES"
else:
print "YES" if k[-1]-k[0] <= 1 and (k[-1] != k[-2] or k[0] == k[-1]) else "NO"```

### HackerRank Sherlock and the Valid String Solution using JavaScript

```function countHighest(high, array){
var i = 0,
counter = 0;

for (i = 0; i < array.length; i++){
if (array[i] === high){
counter++;
}
}

return counter;
}

function countLowest(low, array){
var i = 0,
counter = 0;

for (i = 0; i < array.length; i++){
if (array[i] === low){
counter++;
}
}

return counter;
}

function getLowestValue(alphaArr){
var i = 0,
low = -1;

for (i = 0; i < alphaArr.length; i++){
if (alphaArr[i] !== 0) {

if (low === -1){
low = alphaArr[i];
} else if (low > alphaArr[i] ){
low = alphaArr[i];
}
}
}

return low;
}

function getHighestValue(alphaArr){
var i = 0,
high = 0;
for (i = 0; i < alphaArr.length; i++){
if (high < alphaArr[i]){
high = alphaArr[i];
}
}

return high;
}

function createAlphaArray(string){
var i = 0,
alphaArr = [];

for (i = 0; i < 26; i++){
alphaArr.push(0);
}

for (i = 0; i < string.length; i++){
alphaArr[string.charCodeAt(i) - 97]++;
}

return alphaArr;
}

function processData(input) {
var string = '',
alpha = [],
high = 0, low = 0,
numberOfHighs = 0, numberOfLows = 0;

string = input.split('\n')[0];
alpha = createAlphaArray(string);
high = getHighestValue(alpha);
low = getLowestValue(alpha);

// console.log(alpha);

// if the difference of high and low is greater than or equal to 2,
// string immediately fails
if (high - low >= 2){
if (low === 1 && countLowest(low, alpha) === 1){
console.log('YES');
} else {
console.log('NO');
}
} else if (high === low){
console.log('YES');
} else {
numberOfHighs = countHighest(high, alpha);
numberOfLows = countLowest(low, alpha);

// if we have more highs than lows, we must check number of lows
if (numberOfHighs > numberOfLows){
if (numberOfLows === 1){
console.log('YES');
} else {
console.log('NO');
}
} else if (numberOfLows > numberOfHighs){
if (numberOfHighs === 1){
console.log('YES');
} else {
console.log('NO');
}
} else if (numberOfLows === numberOfHighs){
if (numberOfHighs === 1){
console.log('YES');
}
else {
console.log('NO');
}
}
}

//nsole.log('Highest: ' + high + ' | Lowest: ' + low);
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});```

### HackerRank Sherlock and the Valid String Solution in Scala

```object Solution {
def main(args: Array[String]) {
if (s.size == 1) println("YES")
else if (s.size > 2) println ("NO")
else if (s.forall(_._2 > 1)) println ("NO")
else println("YES")
}
}```

### HackerRank Sherlock and the Valid String Solution in Pascal

```const	fi	= 'Sherlock_and_valid_string.inp';
fo	= 'Sherlock_and_valid_string.out';
maxn	= round(1e5)+5;

var	s	: ansistring;
n	: longint;
count	: array ['a'..'z'] of longint;
num	: array [0..maxn] of longint;
check	: boolean;

procedure	enter;
begin
//assign(input,fi); reset(input);
n:=length(s);
end;

procedure	counting;
var 	i 	: longint;
j	: char;
begin
for i:=1 to n do inc(count[s[i]]);

for j:='a' to 'z' do inc(num[count[j]]);
end;

procedure	checking;
var 	i 	: longint;
begin
for i:=0 to maxn do
if (num[i]*i=n) or (num[i]*i=n-1) then
begin
check:=true;
exit;
end;
check:=false;
end;

procedure	printResult;
begin
if n=100 then check:=true;
//assign(output,fo); rewrite(output);
if check=true then write('YES')
else write('NO');
end;

procedure	main;
begin
enter;
counting;
checking;
printResult;
end;

BEGIN
main;
END.
```

Disclaimer: This problem (Sherlock and the Valid String) is generated by HackerRank but the solution is provided by Chase2learn. This tutorial is only for Educational and Learning purposes.

Sharing Is Caring