HackerRank Sherlock and the Valid String Problem Solution

HackerRank Sherlock and the Valid String Solution

Yashwant Parihar,

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.

HackerRank Sherlock and the Valid String Problem Solution
HackerRank Sherlock and the Valid String Problem Solution

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')

Other Solutions

c C# C++ HackerRank Solutions java javascript python

Leave a Reply