Short Palindrome - HackerRank - world codesprint #5

July 25, 2016

Problem statement

Julia spent 3+ hours to score 13 out of 40 points, she enjoyed the time to work on the problem.

 A few issues: wrong answer, time out, run time error.

 More than 3 submissions, failed to solve time out issue.

 1. C# solution

 2. Add memorization using Dictionary to save time, failed to solve issues.
C# solution 

 3. add one more memorization, failed to solve issues.
C# solution

 4. Review code and then add some comment, and analyse design issues:

C# solution

Review the design, try to find the flaws - a few ideas to improve timeout, no run-time error issue.

review code and then add comment for function countingPalindromes:

/*
	* use two loops
	*
	* get 0110 pairs
	* get 1001 paris
	*
	* Think about DP solution - dynamic programming - not working, too complicate
	*
	* brute force solution:
	* 0 - start char, end char, and then, count how many possibilities
	* Go through O(n*n) case, for any two 0 in pseudo string, check in-between
	*
	* For example:
	* 001010110
	*
	* The above case, there are 5 '0',
	* position of '0' is 0, 1, 3, 5, 8,
	* So, any two '0' combinations are 5*4/2*1 = 10
	*
	* A: 0, 1, in between, there is no chars, n/a
	* B: 0, 3, 2 chars in between - "01", count how many '1' in the substring, only 1.
	* C: 0, 5, 4 chars in between - "0101", two one inside, so how many combination
	* of 11, only 1 choice.
	* D: 0, 8, 7 chars in-between - "0101011", four one's in the substring, how many combination - 4*3/2 = 6 choices
	*/

Add comment for function getPseudoString(...)

/*
	* using 0 and 1 to construct the string
	* 1001
	* 0110
	*
	* There are 26 chars in alphabetic string, any two combination is 26*25/2*1 > 250
	* Instead, using 0 and 1 to stand for two distinct characters.
	* for example, abab
	* 0101
	* So, we can conclude one thing:
	* ababa
	* 01010
	* or
	* 10101
	* So, use memorization, 01010 and 10101 should be same key
	* See if this can solve time out issues - July 25, 2016
	*
	* reverse of string should be same key
	*/

It took Julia more than 3 hours to gain 13/40 point, but learning experience was so great, and she enjoyed the coding experience.

Starting from brute force solution, she made some progress to gain 13 points; go through optimal solution - DP, should be next step.
Statistics:

450 score 40/40

1600  score above 12/40
Total submission: 2180

Facts about HackerRank:
aiming brute force, 30% score.

Dynamic solution:

detail from editiorial notes.  

The idea of DP from the above website: string length is n

pattern to search

xyyx

xy ends position at i - iterate from 1 to n-1,

denote l[i]

yx starts at position i - iteration from i to n-1

denote r2[i]

yx starts at position >=i

denote r[i] = r2[i] + r2[i+1]+...+r2[n-1]

So, to get a solution:

   Iterate i from 1 to n-1
 
   sum of l[i] * r[i]

And one more thing,
          r[i] = r2[i] + r[i+1]

The idea Julia tried on July 24, 2016 -
suppose that T[i] is the short palindrome like "xyyx" at end of string i, how to construct T[i+1]?

Follow up after 8 months

C# code

Follow up 

8/25/2017
I go through the code, and evaluate the code. The fact is that the code is too complicate for a medium level algorithm. Based on the past code contest experience, the code should be very short and concise.

I will put some code review on my last practice, and then write a solution to help the dynamic programming algorithm practice and learning. Make it part of 10 step series.

I’ve tasted success and I’m hungry for more. I’ll prove I’ve got what it takes to win. #CreateYourMark pic.twitter.com/jansdjv9pG

— Lucas Pouille (@la_pouille) May 20, 2016