April 10, 2016
Problem statement:
https://www.hackerrank.com/challenges/string-function-calculation
Time spent: 2:40pm - 3:35pm 20 minutes to think, 20 minutes to write down in C#
Understand the problem, so, here are her thoughts:
Brute force solution:
pass one test case: aaaaaa, return 12,
failed test case:
abcabcddd,
wrong answer - Easy fix, index error on the loop
score 8.89/ 80
one test case: wrong answer
All other test cases time out
https://gist.github.com/jianminchen/09c77ba32b156f765b4debb2bccba0c8
Need to work on KMP, or Boyer-Moore algorithm, see how to make HackerRank happy, score more points.
http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html
blog:
http://juliachencoding.blogspot.ca/search/label/string%20functions%20review
ReplyDeletefunction stringFunctionCalculation(t){
var allPairs = {};
for(var i=0 ; i<t.length ; i++){
for(var j=0 ; j<t.length-i ; j++){
if(allPairs[t.substr(j,i+1)]){
++allPairs[t.substr(j,i+1)];
}
else{
allPairs[t.substr(j,i+1)] = 1;
}
}
}
var max = -1;
for(i in allPairs){
var res = i.length*allPairs[i];
if(max<res){
max = res;
}
}
console.log(max);
}
// only work for those string whose length is less.