Saturday, July 27, 2019

Sherlock and the Valid String - HackerRank - Easiest Solution

Hello everyone, today, while going through the problem of Sherlock & Valid String, I literally tried a lot and was not getting a simple and sober solution.

In fact, when I myself started implementing it, I found that the problem is not that complicated the way the solutions are available in other blogs, so I started the problem and here is the solution I came up with.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function isValid(s) {
  const countMap = {}; const countList = [];
  const arr = s.split('');
  arr.forEach((a) => countMap[a] = (countMap[a] || 0) + 1);
  Object.keys(countMap).forEach(k => countList.push(countMap[k]));
  countList.sort();
  const countSet = new Set(countList);

  const len = countList.length;

  if (countSet.size > 2) {
    return 'NO';
  } else if (countSet.size === 1) {
    return 'YES';
  } else if (countSet.size === 2) {
    const firstNum = countList[0];         const lastNum = countList[len - 1];
    const lastList = countList.slice(1);   const firstList = countList.slice(0, len - 1);
    const lastListSet = new Set(lastList); const firstListSet = new Set(firstList);
    return (
      (lastListSet.size === 1 && firstNum === 1)
      || (lastListSet.size === 1 && lastNum - firstNum === 1)
      || (firstListSet.size === 1 && lastNum - firstNum === 1)
    )
      ? 'YES' : 'NO';
  }
}

Explanation

Suppose the input was aabbc:

  1. Create a countMap with the number of occurrences of each character.
    • countMap = { a: 2, b: 2, c:1 };
  2. Make a list of the values of above maps( not keys ) and sort it.
    • countList = [1, 2, 2]
  3. Convert countList to countSet
    1. countSet = [1, 2]
  4. If (countSet.size > 2) the solution is not possible.
  5. If (countSet.size === 1), we have the "YES"
  6. If (countSet.size === 2), we have to process:
    1. We will create 6 variables for our ease, those are:
      1. firstNum  i.e first number of countList (sorted) = 1 (for our example)
      2. lastList i.e sub array of countList from 1..end = [2, 2]
      3. lastListSet i.e set over lastList, for removing duplicates = [2]
      4. lastNum i.e last number of countList (sorted) = 2
      5. firstList i.e sub array of countList from 0..end-1 = [1, 2]
      6. firstListSet i.e set over firstList, for removing duplicates = [1, 2]
    2. There are only 3 conditions which is "YES" those are:
      1. [ 1, X, X, X, X]
      2. [ X-1, X-1, X-1, X-1, X]
      3. [X, X, X, X, X+1]
    3. For our example 2.1 is true
    4. Apart from them there is no other way, a String will give "YES" and thats what we did

Happy coding,
:)