Intro: Consider a String S that has length greater than 3 elements. Trivialising the problem, Our task is to consider ALL the substrings that have length 3. We will call them Triads. If, in a triad, a character repeats itself - the triad is rich. Further, any string that has the triad is rich. For example, Hello is Rich because, Hello has “ell” and “ell” is rich. World is poor because there is no rich triad in world.
Here is my O(N+Q) solution to the problem.
- Consider the String: “HelloWorld”. The array representation would be |h|e|l|l|o|w|o|r|l|d|. This is a 10 character array.
- Lets build another array of length 7. Lets call this array - NextRichTriadArray.
- Now, lets start with the last three elements (index 7, 8,9) first. Do they make a rich triad?
- If yes, we know that (index 7, 8,9) is a rich triad. So if you are standing at position number 6, you know that the next rich triad is starting at 7.
- Record the above fact by saying 7th element of NextRichTriadArray i.e. NextRichTriadArray[6] is 7.
- If the answer to question in step 3 was no, we know that the next rich triad is not altered. That is to say, no discovery of a rich triad was made.
- Following this approach for HelloWorld we get the NextRichTriadArray|1|2|4|4|9|9|9|
Notice that the Last three elements are 9, 9, 9 indicating that there is no rich triad beyond those points.
This was accomplished in O(n) time and space complexity,
Now time for query.
Consider a query : 1, 4. The query translates to the following:
Consider the substring “Hell” of “Helloworld”, and find out if its rich.
To answer the query, lets look at two scenarios:
- Opening Triad - Triad of first three elements is rich. That is “Hel” is rich. If “Hel” is rich, then “Hell” is also rich. However, if (and since) “Hel” is not rich. Lets move to step 2.
- If the opening triad is not rich - the next rich triad MUST HAVE ENDED before r. If it is not ending before r, it means that there is no rich triad between l and r.
How do we ensure this?
- Lets decrement l and r. We get l and r as 0 and 3 now.
- Lets look at NextRichTriadArray[0] now, what does it store? It stores 1. Okay this means the next rich triad starts at 1. This means it ends at 3.
- Hey, if it ends at 3, and if r is 3 (or for that matter greater than 3) - thats perfect for us. (But lets say the next rich triad started at 2. This means it ends at 4, in this case - since r is only 3 - we can conclude that the whole substring has no rich triad).
Thus we see that each query takes 4 comparisons and 4 lookup - which is O(1) - constant time. q queries would take O(q) time.
Conclusion: Problem solved with O(n+q) time and O(n) space.
Link to my solution with comments: CodeChef: Practical coding for everyone
Interesting variation of this problem is possible , if queries of update each character or update range of characters is allowed.
