# Sheokand and String(SHKSTR) TLE

While solving this question I first used a Map (Key: Character, Value: TrieNode) to solve the problem. Considering O(1) insertion and lookup, my code should not have resulted in TLE but when I used an array of length 26 to store trie nodes, the code got accepted. So should I avoid using maps or dictionaries in CP and why? Is this because its time complexity for insertion and lookups is not exactly O(1)?

Solution using Map: 30 points

Solution using array of length 26: 100 points

The O(1) doesnâ€™t mean it is fast enoughâ€¦ The time taken by earth for one revolution around the sun is O(1)
infact everything periodic is O(1)â€¦ As the time took by earth to revolve around sun wonâ€™t change by the â€ścurrent yearâ€ť
and hence it is O(1)=constant.
Even time taken for rotation is also O(1).
So understand there is a difference between both O(1)'s. Both are constantâ€¦ but one constant is large enoughâ€¦ And another is notâ€¦
Hence my advice is not to use map set unnecessarilyâ€¦ Use them whenever they are requiredâ€¦
Map and sets are meant when â€śnâ€ť is large enough so u need something that doesnâ€™t take more time with more â€śnâ€ť and hence maps and sets were usefulâ€¦ but for 26 characters it is not useful at all

Consider using even faster IO for both reading and writing.

I submitted your code with my even faster IO. [Your code with my IO][1]. Notice the difference in speed.
I havenâ€™t gone through your code, but I solved this using Map(Character, TrieNode) myself.
You can have a look at my soln here

``````
[2]. Have added useful messages. Let me know if you face issues!

[1]: https://www.codechef.com/viewsolution/18878084
[2]: https://www.codechef.com/viewsolution/18878178``````

@l_returns also has a valid point. Some questions really need to you squeeze the bajezuz out of the hardware. CHSIGN in prev month competition required a lot of optimisation (not related to core logic). You can continue using maps. However if you notice that 1 or 2 are TLE and AC ones are close to Time Limit, consider using alternatives like arrays (or perhaps a better logic <- No shit @kukreja_vlk)

1 Like