Difficulty: Easy-Medium
Pre-requisite Knowledge: Trie Data Structure/Hashing
Time Complexity:
(O(N^2))
Problem:
You are given an integer N denoting the size of the array and a circular array of N values. We need to find the number of distinct subarrays in the circular array in both the directions i.e; clockwise and anti-clockwise.
Quick Explanation:
Store the suffixes in a suffix trie and count the number of nodes in the trie.
Detailed Explanation:
The first task is to convert the given array into a string which can be done by appending each of the digit character to an empty string one by one serially.
As the question is based on a circular list of elements, we append a copy of the string to the original string again so that all the substrings are covered by a single string.
Now, generate each substring of the string whose length is not greater than N and insert it into the trie data-structure. This trie data structure will have maximum 10 children nodes and not more than that. So, we create a trie structure accordingly. As, the question also deals with substrings in the anti-clockwise too, reverse the string and repeat the suffix-inserting process again.
Now, simply count the number of nodes in it which denotes the number of distinct substrings possible.
There is an alternative using hashing which is depicted in the tester’s solution. In this case, Robin Karp hashing is used.
Solution Links: