### Question

Find the substring of length 3 which is present in the reverse order from the string.

Ex: if the string is abcdcba (cba is the reverse of abc) so we should return cba.

### Solution

**HashMap (recommended)**. Hash all substrings of length 3. O(n). Look up all reverse substrings of length 3 in this hash set. O(n) time and O(n) space.**KMP Algo**. Take every substring of length 3. Reverse it and find it in the input using KMP. O(n^{2}) time and O(1) space.**Build suffix tree**of height 3. Then in reverse order, check triplets.

The 3 solutions above all work well. Pick the one you love.