Sign in
Log inSign up

Sherlock and the Valid String (Solution with Javascript)

Opeoluwa Siyanbola's photo
Opeoluwa Siyanbola
·Apr 18, 2021·

2 min read

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.

Link to Problem

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.