HackerRank: String - Sherlock and anagrams (I)

March 27, 2016

Problem statement:

https://www.hackerrank.com/challenges/sherlock-and-anagrams

Difficulty: Moderate

This problem solving gets hot. Julia found something she struggled a lot. When Julia spent more than 2 hours on a problem in the Saturday evening, she knew that she is in trouble. She needs to be trained, and she needs a mentor.

Time Spent: March 26, 2016 Saturday evening 9:30 - 11:30
                                               Sunday morning  9:00 - 12:00 

Several mistakes to fix:

1. Julia, improve your analysis on test cases from HackerRank

2. Julia, understand Anagram requirement.

3. loop index issues

Julia's practice:

https://gist.github.com/jianminchen/dd2290f3a7b67e5168c9

Go over test case again:

1. abba,

Let's say S[i, j] denotes the substring(i, j-i+1)

S[0,1] = "ab",

S[0,2]="abb",

S[1,1] = "b"

S[4,4] = "b"

S[1,2] = "ab"

S[3,4] = "ba"

For S = abba, anagrammatic pairs are:

{S[1,1], S[4,4]},     //

{S[1,2], S[3,4]},

{S{2,2], S{3,3]},

{S[1,3], S[2,4]}

Notice that substring can be selected by first char of string, choice of n-m, n is string length, m is substring length.

substrings can be overlapped, but still are anagrammatic pairs.

S[1,3] and S[2,4] are overlapped, but are the anagrammatic pair.

Sample test case "abba", output should be 4, but Julia got 3. Spent time to fix index error.

2. sample case: ifailuhkqq

should be: 3

Julia got 4

Actually, Julia, you should simplify the test case first.

it is the same as ifailqq,

also it is the same as ifilqq

How many anagramammatic pairs in "ifilqq"

"i","i" - S[1, 1] and S[3,3]

"if","fi" - S[1, 2] and S[2,3] <- warm up anagram definition: same chars with same counts

"q", "q"

but 2 'i' char in the string "ifilq",

  1 'i' char in the string "filqq",

Actually, the test case can be simplified using:
"abacdd", the pairs are (a,a), (ab, ba), (d,  d). That is very simple and understandable! 

"abacd" and "bacdd" are not anagrams, because two 'a' in first string, but 1 a in second string. 
so two strings are not anagram.

Julia, what you spent time on:

1. List<int> constructor issue - 10 minutes, List<int>(i)

2. 10 minutes to figure out that you should work on anagrams strings 

3. 10 minutes to write, 15 minutes to debug - Wrote a wrong anagram function

"ifilq" is not an anagram of "filqq", sample test case No. 2 should be 3

Julia is not very strong on testing software, she writes the software and puts it on. The software 
she writes can be improved tremendously, but she needs to find out what to improve. 

To be continued.