Skip to content

Instantly share code, notes, and snippets.

@nickangtc
Last active May 18, 2023 16:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nickangtc/d59eed444456632119bc6b65d66d225b to your computer and use it in GitHub Desktop.
Save nickangtc/d59eed444456632119bc6b65d66d225b to your computer and use it in GitHub Desktop.
Hackerrank medium: Sherlock and the Valid String
// 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