Last active
May 18, 2023 16:03
-
-
Save nickangtc/d59eed444456632119bc6b65d66d225b to your computer and use it in GitHub Desktop.
Hackerrank medium: Sherlock and the Valid String
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem | |
function isValid(s) { | |
const occurrences = {}; | |
for (let i = 0; i < s.length; i++) { | |
const alphabet = s.charAt(i); | |
occurrences[alphabet] = occurrences[alphabet] | |
? occurrences[alphabet] + 1 | |
: 1; | |
} | |
const groupedByCount = Object.keys(occurrences).reduce( | |
(grouped, alphabet) => { | |
const count = occurrences[alphabet]; | |
const updatedGroup = grouped[count] | |
? [...grouped[count], alphabet] | |
: [alphabet]; | |
return { | |
...grouped, | |
[count]: updatedGroup, | |
}; | |
}, | |
{} | |
); | |
const uniqueNumberOfCounts = Object.keys(groupedByCount).length; | |
if (uniqueNumberOfCounts === 1) { | |
// all alphabets have the same number of occurrences | |
return "YES"; | |
} else if (uniqueNumberOfCounts > 2) { | |
// there are more than 2 different number of occurrences, which means | |
// removing 1 alphabet will never do the trick anyway | |
return "NO"; | |
} | |
// at this point, we only have 2 different counts of alphabets | |
if (groupedByCount["1"] && groupedByCount["1"].length === 1) { | |
// eliminate the alphabet completely by removing its single occurence | |
return "YES"; | |
} | |
const counts = Object.keys(groupedByCount); | |
const countA = counts[0]; | |
const countB = counts[1]; | |
const alphabetsWithCountA = groupedByCount[countA]; | |
const alphabetsWithCountB = groupedByCount[countB]; | |
// if in the remaining 2 groups, at least 1 of them has only 1 alphabet with that | |
// number of occurrences, e.g. 5 occurrences of 'a' | |
// then, check the counts of the 2 groups. If their counts are off by 1, | |
// then we can safely assume that removing 1 occurrence of that alphabet | |
// will make Sherlock happy. | |
if (alphabetsWithCountA.length === 1 || alphabetsWithCountB.length === 1) { | |
return Math.abs(countA - countB) === 1 ? "YES" : "NO"; | |
} | |
return "NO"; | |
} | |
// ===== Below this line were self-talk comments I used when constructing the solution ===== | |
// TEST CASES | |
// a === YES | |
// ab === YES | |
// aaaaaaaaaaa === YES | |
// aabbaab === YES | |
// aabbaabbb === YES | |
// aabbaabbbb === NO | |
// 4,4,4,4,3 => NO (can only remove, not add 1 char) | |
// 4,4,4,4,5 => YES (remove 1 char) | |
// 4,4,4,4,1 => YES (remove 1 char, which eliminates the alphabet altogether) | |
// 4,4,4,4,5,5 => NO (can only remove not more than 1 char) | |
// 4,5 => YES (can remove 1 char) | |
// e.g. A { 5: ['a','b','c'], 4: ['e'] } => NO | |
// e.g. B { 5: ['a','b','c'], 6: ['e'] } => YES | |
// e.g. C { 5: ['a','b','c'], 1: ['f'] } => YES | |
// e.g. D { 5: ['a','b','c'] } => YES | |
// e.g. E { 5: ['a'], 2: ['b'], 10239: ['c'] } => NO | |
// e.g. F { 5: ['a', 'g'], 2: ['b', 'c', 'd'] } => NO |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment