Sherlock and the Valid String (Solution with Javascript)
Problem
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.
Explanation
if the frequency of all member of the string are equal return YES
S=abc
{a:1, b:1, c:1} frquencies: [1,1,1] return YES since all frequencies are equal
S=abcc
{a:1, b:1, c:2} [1,1,2-1=1] return YES since we have the oppurtunity to minus one from any of the frequencies now all frequencies are equal
S=abccc
{a:1, b:1, c:3} [1,1,3-1=2] return NO since we have the oppurtunity to minus one from any of the frequencies, all frequencies in this case are not equal.
My solution using javascript.
function isValid (s) {
let hash = {};
let max, min;
let minCount = 0;
let maxCount = 0;
///Get the frequencies of each characters
for (let i = 0; i < s.length; i++) {
let key = s[i];
if (hash[key]) {
hash[key]++;
} else {
hash[key] = 1;
}
}
//Push all strings in to an array
let frequencies = [];
for (let key in hash) {
frequencies.push (hash[key]);
}
//Sort the array and get the max and min frequency
frequencies.sort ();
min = frequencies[0];
max = frequencies[frequencies.length - 1];
//Get the no of max count and min count for the frequency
for (let i = 0; i < frequencies.length; i++) {
if (frequencies[i] === max) {
maxCount++;
}
if (frequencies[i] === min) {
minCount++;
}
}
///Make our validation check
if (min === max) {
return 'YES';
}
if (max - (min - 1) == max && minCount === 1 && maxCount !== 1) {
return 'YES';
}
if (max - min !== 1) {
return 'NO';
}
if (maxCount === minCount) {
return 'NO';
}
if (maxCount === 1 || minCount === 1) {
return 'YES';
}
return 'NO';
}
I will love to hear your opinion about the solution and also if there is a more performant solution to the problem.
Thank you.