Skip to content

Instantly share code, notes, and snippets.

@Oluwa-nifemi
Created September 24, 2019 17:35
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 Oluwa-nifemi/1e9278e7543e8d83a254b60cb18fac90 to your computer and use it in GitHub Desktop.
Save Oluwa-nifemi/1e9278e7543e8d83a254b60cb18fac90 to your computer and use it in GitHub Desktop.
Solution to Hackerrank Weighted Strings Problem - https://www.hackerrank.com/challenges/weighted-uniform-string/problem
function weightedUniformStrings(s, queries) {
const count = (string) => string.split('').reduce((acc,letter,index) => {
if(!acc[letter]){
acc[letter] = [1]
}else{
if(string[index - 1] && string[index - 1] === letter){
acc[letter][acc[letter].length - 1] += 1
}else{
acc[letter].push(1)
}
}
return acc
},{})
const letterCounts = count(s)
return queries.map(query => {
for(let i = 1;i <= 26;i++){
if(Number.isInteger(query/i)){
const countsArray = letterCounts[String.fromCharCode(96 + i)]
if(countsArray && countsArray.find(a => a >= (query/i))){
return "Yes"
break;
}
}
}
return "No"
})
}
@Oluwa-nifemi
Copy link
Author

So here's my reasoning
If you take each number in the queries array and divide it by the weight of each letter.
You check whether it's an integer if yes we keep going.
You check whether the integer it gives you is smaller than or equal to the number of times there was a run of that particular letter
For example Number 12 String aaabbccdddda
We have 3 a's 2 b's 2 c's 3 d's 1 a
12/1 = 12 Do we have up to 12 a's? no
We keep going until we reach d (12/4 = 3), we have up to 3 d's meaning that at some point we'd have had 3 * 4 for weight of d's and that's a valid yes. The way I generate the runs is the count function which I'll explain below.
The count function is meant to return an object with keys of alphabets which have arrays representing their runs (eg: {a: [3,1,4]}
The count function uses the reduce function with a default of an empty object. Initially I check whether the letter exists in the object.
If it doesn't I just create an instance of it with a value of [1]. Representing a current run of 1
If it does I check whether the previous value matches the current value. If it does I add 1 to the last value of the array for the current alphabet.
If it doesn't I push 1 into the array for that particular key
(eg If we have ffd, we'd have created [1] for key f on the first run and we'll add 1 to it so now we have key f with array [2] representing a run of 2. Then the next one is d we create key d with [1]. We go again we have f the previous one was d so we push 1 into the key f's array so the object looks like
{
f: [2,1],
d: [1]
}
representing a run of 2 and 1 for f and a run of 1 for d.
)
We can then use the object generated by the function to check our numbers after division using the find function to find whether there was any run greater than or equal to the divided value.
So yeah that's my thought process
Apologies for it being messy

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment