IEMCO7F | Editorial by shah

IEMCO7F | Editorial by shah_entrance

**Idea:**  Let’s define an array **RES**, where **RES[i][j]** represents the total number of eligible pair of strings which starts at index **i** and ends at index **j**. So at any time we will be answer to any query in **O(1)**.
We need to build a data structure such that given any string **S** it can tell us how many inserted strings are already there which match with string **S** in **O(maximum length of S)** complexity.
We can do this using trie data structure. For each of the suffix of a string we must build a trie.
Now sort all the names in increasing order of time and iterate through one by one. When a person enters the event we will insert his name in that data structure, and when he leaves we will delete them again.
Now let’s see how can handle this **insert** and **delete** operation.
Let’s say a person **S** has entered the event. Now for each **substring S(L,R)** of string **S** insert this substring in **TRIE[L]**. Here **L** is the starting position and **R** is the ending position of **substring(L,R)**.
Now how this new insertion change the **RES[L][R]** ?
Let’s take **K**= the number of string in **TRIE[L] **which match with **substring(L,R)** before inserting it. So **C(K,2)** was included in **RES[L][R]** for this particular substring.
Here **C(K,2)**= no of ways to select any pair of items from **K** items.
But after the insertion of it the new count will be **(K+1)** so the new result is supposed to be **C(K+1,2)** now.
So to adjust the result remove **C(K,2)** and add **C(K+1,2)** in **RES[L][R]**=RES[L][R]-C(K,2)+C(K+1,2).
The deletion process is similar to the insertion. As we are deleting now the new value of **K** will be **K-1**. We handle the other things accordingly.
**Complexity :** We can iterate through each suffix in **O(length of the suffix)** and then delete each of the prefix of that suffix in** O(length of the suffix).** Thus we will be able to insert or delete all sub-string of a string in **O(N*(length of the suffix)^2)** complexity.
**Note: **we could also handle the same operations using hashing and unordered_map. As unordered_map is supposed to work in **O(1)**. So the complexity would be the same. But unordered_map works very slowly when there us huge amount of data.

IEMCO7F | Editorial by shah_entrance

Download submission

All caught up!

View submission

Is your resume even shortlisted?