Hello Programmers, In this post, you will Know 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 directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Sherlock and the Valid String Solution
Task
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
YESorNO
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
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;
}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;
}Sherlock and the Valid String Solution in Java
import java.io.*;
import java.util.*;
public class _101HackJuneqA {
public static void main(String args[]) {
InputReader in = new InputReader(System.in);
PrintWriter w = new PrintWriter(System.out);
char s[] = in.readString().toCharArray();
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();
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[8192];
private int curChar;
private int snumChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} 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;
}
public String readString() {
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);
}
}
}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"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);
});Sherlock and the Valid String Solution in Scala
object Solution {
def main(args: Array[String]) {
val s = readLine.groupBy(_.toChar).mapValues(_.length).map(_._2).groupBy(_.toInt).mapValues(_.size)
if (s.size == 1) println("YES")
else if (s.size > 2) println ("NO")
else if (s.forall(_._2 > 1)) println ("NO")
else println("YES")
}
}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);
readln(s);
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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.