Round 1
Questions: You 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].
Suppose s1 = "aba" and s2 = "abbbaaa", they both are magical pairs, but if s1 = "abc" and s2 = "bcd", they both are not magical pairs.
Candidate's Approach
- Initially provided a brute force solution using a set to count distinct characters.
- Then presented an optimized solution using BitMask.
- Received hints from the interviewer indicating that a binary search approach could also be applied, but struggled to implement it.
Interviewer's Feedback
- The interviewer acknowledged the brute force and BitMask solutions but indicated there was a more efficient method.
- Suggested that the candidate explore binary search for a potential solution.