Sherlock and the Valid String
Sherlock and the Valid String
+ 42 comments The problem description should include that you can remove every occurence of a character and the examples should support this. The current description is misleading.
+ 30 comments Here is my solution in Java. It passed all test cases here. IMHO, this is not a straight forward problem.
static String isValid(String s) { final String GOOD = "YES"; final String BAD = "NO"; if(s.isEmpty()) return BAD; if(s.length() <= 3) return GOOD; int[] letters = new int[26]; for(int i = 0; i < s.length(); i++){ letters[s.charAt(i) - 'a']++; } Arrays.sort(letters); int i=0; while(letters[i]==0){ i++; } //System.out.println(Arrays.toString(letters)); int min = letters[i]; //the smallest frequency of some letter int max = letters[25]; // the largest frequency of some letter String ret = BAD; if(min == max) ret = GOOD; else{ // remove one letter at higher frequency or the lower frequency if(((max - min == 1) && (max > letters[24])) || (min == 1) && (letters[i+1] == max)) ret = GOOD; } return ret; }
+ 18 comments Good problem, but I'd probably mark it as easy or medium, not difficult.
+ 2 comments I think this problem merits the medium rating it wound up at. It is very easy to say "this is easy" and throw an overly simple code at it that misses a test case or two. That both makes you appreciate that it probably is a medium problem and that test case writers are terribly underappreciated.
Any non-trivial work, you can't overestimate the importance of having great test cases that don't miss weird corner cases and funny things that will "hardly ever happen" == "all the time" when huge amounts of data come at you.
Even in my not-quite-big-data career I've seen the craziest things happen because with still huge amounts of real data coming in to your software the incredibly rare conicidences still happen and break your code which is rock-solid unless one of those bizarre corner cases hits it and brings it down. Hooray for sufficient test cases and those hard-working underappreciated heros who write them.
+ 5 comments My code failed only on Test case 14. It turns out that this test case has a string of 100,000 character long. I'm using Java where the limit of string length is only 0xFFFF or 65535. Admin may want to look into this test.
Sort 1764 Discussions, By:
Please Login in order to post a comment