# HackerRank Sherlock and the Valid String problem solution

In this HackerRank Sherlock and the Valid String Interview preparation kit problem, You need to complete the isValid function.

## Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the isValid function below.
def isValid(s):
d = Counter(s)
counts = Counter(d.values())
if len(counts) == 1:
return "YES"
elif len(counts) > 2:
return "NO"
else:
max_v = max(counts.values())
k1, k2 = counts.keys()
if (max_v == len(d) - 1):
if (abs(k1 - k2) == 1):
return "YES"
elif (min(k1, k2) == 1):
if counts[1] == 1:
return "YES"
else:
return "NO"
else:
return "NO"
else:
return "NO"

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

s = input()

result = isValid(s)

fptr.write(result + '\n')

fptr.close()

## Problem solution in Java Programming.

import java.io.*;
import java.util.*;
import java.math.BigInteger;
import java.util.Map.Entry;

import static java.lang.Math.*;

public class Solution extends PrintWriter {

boolean solve() {

char[] str = nextLine().toCharArray();

int m = 256, n = str.length + 1;
int[] cnt = new int[m];
for (char c : str) {
++cnt[c];
}

int[] f = new int[n];

for (int val : cnt) {
++f[val];
}

int x = 0;
for (int i = 1; i < n; i++) {
if (f[i] > 0) {
++x;
}
}

if (x == 1) {
return true;
}

if (x > 2) {
return false;
}

int y = 0;

for (int i = 2; i < n; i++) {
if (f[i] > 0) {
++y;
}
}

if (y == 1 && f[1] == 1) {
return true;
}

int z = 0;

for (int i = 2; i < n; i++) {
if (f[i] == 1 && f[i - 1] > 0) {
++z;
}
}

return z == 1;
}

void run() {
println(solve() ? "YES" : "NO");
}

int[][] nextMatrix(int n, int m) {
int[][] matrix = new int[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
matrix[i][j] = nextInt();
return matrix;
}

String next() {
while (!tokenizer.hasMoreTokens())
tokenizer = new StringTokenizer(nextLine());
}

boolean hasNext() {
while (!tokenizer.hasMoreTokens()) {
String line = nextLine();
if (line == null) {
return false;
}
tokenizer = new StringTokenizer(line);
}
return true;
}

int[] nextArray(int n) {
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = nextInt();
}
return array;
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
try {
} catch (IOException err) {
return null;
}
}

public Solution(OutputStream outputStream) {
super(outputStream);
}

static StringTokenizer tokenizer = new StringTokenizer("");
static Random rnd = new Random();

public static void main(String[] args) throws IOException {
Solution solution = new Solution(System.out);
solution.run();
solution.close();

}
}

### Problem solution in C++ programming.

#include <bits/stdc++.h>

using namespace std;

char s[1234567];

int main() {
scanf("%s", s);
int n = strlen(s);
vector <int> cnt(26, 0);
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']++;
}
for (int i = 0; i <= 26; i++) {
if (cnt[i] == 0) {
continue;
}
if (i < 26) {
cnt[i]--;
}
vector <int> a = cnt;
sort(a.begin(), a.end());
int res = a[25];
bool ok = true;
for (int j = 0; j < 26; j++) {
if (a[j] != 0 && a[j] != res) {
ok = false;
break;
}
}
if (ok) {
puts("YES");
return 0;
}
if (i < 26) {
cnt[i]++;
}
}
puts("NO");
return 0;
}

### Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int test(int *alphabet)
{
int num = alphabet[0];
int i;

for(i = 1; i < 26; i++)
{
if(alphabet[i] == num)
{
num = alphabet[i];
}
else if(alphabet[i] != num && alphabet[i] != 0)
return 0;
}
return 1;
}

int main() {

int i = 0;
int alphabet[26];
int c = EOF;
int num, pass = 0;

for(i = 0; i < 26; i++)
alphabet[i] = 0;

while (( c = getchar() ) != '\n' && c != EOF)
{
alphabet[c - '0' - 49]++;
}

if(test(alphabet))
printf("YES\n");
else
{
for(i = 0; i < 26; i++)
{
if(i != 0)
alphabet[i - 1]++;
alphabet[i]--;
if(test(alphabet))
{
printf("YES\n");
pass = 1;
break;
}
}
if(pass == 0)
printf("NO\n");
}

return 0;
}

### Problem solution in JavaScript programming.

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);
});

1. This comment has been removed by the author.

2. I'm glad I work with a modern language that has a lot of handy, built-in functions. Using those I get shorter, more concise and readable code:

private fun isValid(s: String): String {
val histogram = s.toList()
.groupingBy { it }.eachCount() // char -> count, e.g. abccc is { 'a' -> 1, 'b' -> 1, 'c' -> 3)
.values.groupingBy { it }.eachCount() // counts -> count, e.g. abccc is { 1 -> 2, 3 -> 1)
.toSortedMap()

val min = histogram.keys.first()
val max = histogram.keys.last()

return when {
histogram.size > 2 -> "NO" // more than 2 frequencies
histogram.size == 1 -> "YES" // all the same frequencies
min == 1 && histogram[min] == 1 -> "YES" // least frequent character appears just once
max - min == 1 && histogram[max] == 1 -> "YES" // most frequent character
else -> "NO"
}
}