I recently gave Google Onsite Interview and I was asked this question. Was able to give the brute force solution using set and then gave the optimized solution using BitMask.\n\n\nBut the interviewer said there is another efficient approach apart from bitmask.\n\n\nHe gave me hints and I was able to figure out that I have to use Binary Search but couldn\'t come up with how to apply binary search.\n\n\nCan anyone help to provide the solution?\n\n\nWhat do you think my outcome would be for this interview? (in terms of Hire, Leaning Hire etc.)\n\n\nYou have been given a string s. Two strings s1 and s2 are considered to be magical string pairs if the number of distinct characters in s1 is equal to s2. Given a string s, find the number of triplets i, j, k which satisfy this condition. The string s1 is from s[i, j] and s2 from [j+1, k].

I recently gave Google Onsite Interview and I was asked this question. Was able to give the brute force solution using set and then gave the optimized solution 