Problem statement:
https://www.hackerrank.com/contests/hourrank-6/challenges/bear-and-steady-gene
Editorial:
Let's first think when Limak can choose some particular interval (substring). We should care about the remaining letters, both in the prefix and the suffix. If there are more than remaining letters of one type then we can't get a steady string. Otherwise, we know exactly how many letters of each type are missing and we can fill the removed interval with these exact letters. So, the interval can be chosen only if the remaining part doesn't contain more than letters of some type.
For each possible starting index of the interval let's find the nearest (leftmost) possible ending index. You can create four segment trees, one for each letter. Then, for fixed interval you can check in whether there are at most remaining letters of each type. So, for each starting index you can binary search the earliest good ending index. Segment trees and binary search give us . Let's make it faster.
First thing is to get rid of segment trees. It's enough to store prefix (and maybe suffix) sum for each letter, so you don't need segment trees anymore. It's ok to get AC but you can change one more thing. As we move with the starting index to the right, the ending index also moves to the right (or it doesn't change). So, we can use the two pointers technique to get solution. You can check codes below for details.
Julia's practice:
https://gist.github.com/jianminchen/80723bae951328a690bb
score 15 out of 50, there are 2 run time error, failed a few of test cases. The implementation is no better than brute force solution.
C# code implementation to study:
https://gist.github.com/jianminchen/153eab0defae014842e8
Readable code, with some analysis.
https://gist.github.com/jianminchen/fae9142eff9a6f9643fc
Java code implementation to study:
https://gist.github.com/jianminchen/d52ced38de0bffa2d9e8
C++ code to study:
https://gist.github.com/jianminchen/d7370b7e73013ee708be
write this one as well <- Great code, very readable!
https://gist.github.com/jianminchen/c6b51207f9cc9b083573
https://gist.github.com/jianminchen/80638c0db328d0098f3b
Binary search algorithm: (Java)
https://gist.github.com/jianminchen/d01faa03ca9b06696db3
Comment:
The brute force solution will not pass the test cases.
It takes a lot of time to read 108 people's code - all scores 50 / 50. It is fun to read all 108 solution scoring 50/50.
Julia, take time to play with this algorithm.
Nov. 28, 2016
Study the code:
https://gist.github.com/jianminchen/c4f1c84c984e58fdcdc467e6f28d84e3
code review:
1. line 26, int[] a = new int[1007];
1007 is not meaningful, we know the size should be bigger than 'Z', and we only need the array of size 4
2. variable i and index are not meaningful. There are two loops.
3. valid function from line 49 - line 58
line 52 - 55 - four constant chars are used.
Review the code and make the change:
https://gist.github.com/jianminchen/124b33e3d7aa0276e7b6ea4542c8ad5b
1. line 26 - 36, add 4 test cases, with 4 postcondition assertions
2. function name is changed to minChange
3. line 61, array of size 4 is declared instead of 1007
4. function indexOf() is added
5. variable names are changed, left, right, two pointers, move forward only
6. add two explanation variable c1, c2 to advoid complicated expression.
7. valid function is declared using a for loop.
Based on the code review on this post:
http://codereview.stackexchange.com/questions/142808/quick-sort-algorithm/142853#142853
answered by Eric Lippert
No comments:
Post a Comment