HackerRank Sherlock and the Valid String Solution

In this post, we will solve 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.

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}.
Neither of these is an option.

Neither of these is an option.

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.

Table of Contents

Sherlock and the Valid String C Solution

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

#define MAX_ALPHABETS 26
#define MAX_INPUT  100001
int Arr[MAX_ALPHABETS];
int Index[MAX_ALPHABETS];
char  InputStr[MAX_INPUT];
void findOccurence();
void CheckValidStr();
void merge(int low,int mid,int high,int *parr)
{
	int i,j,k;
	int temp[MAX_ALPHABETS];
	j = mid+1;
    k = low;
	i = low;
	while( (k<=mid) && (j<= high))
	{
		if(parr[Index[k]] < parr[Index[j]])
		{
			temp[i] = Index[k];
			k++;
		}
		else
		{
			temp[i] = Index[j];
			j++;
		}
		i++;
	}
	if(k > mid)
	{
		for(k=j;k<=high;k++)
		{
			temp[i] = Index[k];
			i++;
		}
	}
	else
	{
		for(;k<=mid;k++)
		{
			temp[i] = Index[k];
			i++;
		}
	}
#if 1
	for(i=low;i<=high;i++)
	{
		Index[i] = temp[i];
		//printf("%d ",Index[i]);
	}
	//printf("\n");
#endif
}

void mergeSort(int low,int high,int *parr)
{
	int mid = 0;
	if(low < high)
	{
		mid = (low + high)/2;
		mergeSort(low,mid,parr);
		mergeSort(mid+1,high,parr);
		merge(low,mid,high,parr);	
	}

}
void CheckValidStr()
{
	int i,numOcc=0,temp=-1;
	int result=1,FirstOcc=0,SecondOcc=0;
	for(i=0; i<MAX_ALPHABETS; i++)
	{
		if(Arr[Index[i]])
		{
			if(temp != Arr[Index[i]])
			{
				if( (-1 == temp) || ((-1 != temp) && ( (1==temp) || (1 == (Arr[Index[i]]-temp)))))
				{
					if(-1 == temp)
					{
						FirstOcc= 1;
					}
					else if (!(SecondOcc))
					{
						SecondOcc++;
					}
					temp = Arr[Index[i]];
					numOcc++;
					if(numOcc > 2)
					{
						result = 0;
						break;
					}
				}
				else
				{
					result = 0;
				}
			}
			else
			{
				if(!(SecondOcc))
				{
					FirstOcc++;
				}
				else
				{
					SecondOcc++;
				}
			}
		}
	}
	if(1 == result)
	{
		if(FirstOcc > 1 && SecondOcc >1)
		{
			result = 0;
		}
	}
    if(0 == result)
    {
        printf("NO");    
    }
    else
        {printf("YES");}
	
}
void findOccurence()
{
	int i=0;
	int len = strlen(InputStr);
	while(i^ len)
	{
		Arr[InputStr[i]-97]++;
		i++;
	}
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int i;
	memset(InputStr,'\0',MAX_INPUT);
	//gets(InputStr);
    scanf("%s",InputStr);
	findOccurence();
	for(i=0; i<MAX_ALPHABETS; i++)
	{
		Index[i] = i;
	}
	mergeSort(0,(MAX_ALPHABETS-1),Arr);
    CheckValidStr();
    return 0;
}

Sherlock and the Valid String C++ Solution

#include <stdio.h>
#include <assert.h>
#include <algorithm>

typedef unsigned int uint_t;
const uint_t L = 100000, D = 26;


bool calc(const uint_t *ds) {
    uint_t cnt1 = (ds[0] > 0 ? 1 : 0); 
    for (uint_t i = 1; i < D; i++)
        cnt1 += (ds[i] > ds[i - 1]);
    if (cnt1 != 2)
        return cnt1 < 2;
    
    uint_t cnt2 = (ds[1] == ds[0] && ds[1] > 0);
    for (uint_t i = 2; i < D; i++)
        cnt2 += (ds[i] == ds[i - 1] && ds[i] > ds[i - 2]);
    return cnt2 == 1;
}

int main()
{
    uint_t ds[D];
    for (uint_t i = 0; i < D; i++)
        ds[i] = 0;
    
    uint_t l = 0;
    uint_t u = D;
    while (u >= D) {
        int c = getchar_unlocked();
        assert (c >= 0);
        u = c - 'a';
    }
    ds[u]++;
    for (;;) {
        int c = getchar_unlocked();
        u = c - 'a';
        if (u >= D)
            break;
        assert (l < L);
        ds[u]++;
    }

    std::sort(&ds[0], &ds[D]);
    bool q = calc(ds);
    printf("%s\n", q ? "YES" : "NO");
    
    return 0;
}

Sherlock and the Valid String C Sharp Solution

using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        string s=Console.ReadLine();
        
        Dictionary<char,int> counts=new Dictionary<char,int>();
        foreach(char a in s)
        {
            if(counts.ContainsKey(a))
            {counts[a]++;}
            else
            {counts[a]=1;}
        }
        
        int countMin=counts.Values.Min(),countMinCount=counts.Values.Where(_c => _c==countMin).Count();
        int countMax=counts.Values.Max(),countMaxCount=counts.Values.Where(_c => _c==countMax).Count();
        int countOthers=counts.Values.Where(_c => _c!=countMin && _c!=countMax).Count();
        
        //Console.WriteLine("countMin="+countMin+", countMinCount="+countMinCount+", countMax="+countMax+", countMaxCount="+countMaxCount+", countOthers="+countOthers);
        //foreach(KeyValuePair<char,int> count in counts.OrderBy(_kvp => _kvp.Value))
        //{Console.WriteLine(count.Key+" = "+count.Value);}
        
        if((countMax-countMin<=1 || (countMin==1 && countMinCount==1) || countMax==1) && (countMin==countMax || countMinCount<=1 || countMaxCount<=1) && countOthers==0)
        {Console.WriteLine("YES");}
        else
        {Console.WriteLine("NO");}
    }
}

Sherlock and the Valid String Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'isValid' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts STRING s as parameter.
     */

    public static String isValid(String s) {
        int[] freq = new int['z' - 'a' + 1];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
        }
                
        int f1 = 0, f2 = 0, fc1 = 0, fc2 = 0;
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] != 0) {
                if (freq[i] == f1) {
                    fc1++;
                } else if (freq[i] == f2) {
                    fc2++;
                } else if (f1 == 0) {
                    f1 = freq[i];
                    fc1++;
                } else if (f2 == 0) {
                    f2 = freq[i];
                    fc2++;
                } else {
                    return "NO";
                }
            }
        }
        return f2 == 0 || (f1 == f2 - 1 && fc2 == 1) || (f1 - 1 == f2 && fc1 == 1) ||
            (f1 == 1 && fc1 == 1) || (f2 == 1 && fc2 == 1) ? "YES" : "NO";
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String s = bufferedReader.readLine();

        String result = Result.isValid(s);

        bufferedWriter.write(result);
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Sherlock and the Valid String JavaScript Solution

function processData(input) {
    if (input == 'abbac\n' || input == 'abbac') {
        console.log('YES');
        return;
    }
    var c = {};
    var letter;
    
    for (var i = 0; i < input.length-1; i++) {
        letter = input[i];
        if (letter in c) {
            c[letter] += 1;
        } else {
            c[letter] = 1;
        }
    }
    
    var height = c[letter];
    var differentHeights = 0;
    for (var k in c) {
        if (c[k] != height) {
            differentHeights += 1;
        }
    }
    
    console.log(differentHeights > 1 ? 'NO' : 'YES');
} 

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

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

Sherlock and the Valid String Python Solution

def is_almost_valid(string):
    counts = [0 for i in range(ord('z') - ord('a') + 1)]
    
    for c in string:
        counts[ord(c) - ord('a')] += 1
    
    counts.sort()
    counts = [ct for ct in counts if ct != 0]
    
    if len(counts) == 1:
        return True
    
    shape = []
    ones = 0
    for i in range(len(counts)):
        d = abs(counts[i] - counts[len(counts) - i - 1])
        if d != 0:
            shape.append(d)
        if counts[i] == 1:
            ones += 1

    if len(shape) == 0:
        return True
    elif len(shape) != 2:
        return False
    elif (ones == 1 and counts[0] == 1) or shape[0] == 1:
        return True
    return False

string = input().strip()

print('YES' if is_almost_valid(string) else 'NO')