Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Happy Spell

By rohijulislam · Limits 1s, 512 MB

"Let me give you a clue. The happiest man on Earth would look into the mirror and see only himself, exactly as he is." - was the words Albus Dumbledore told Harry Potter long ago.

But why is Harry reminiscing about the mirror anyway? He has come to help his friend Hermione Granger in inventing a new spell to battle dementors. Being a talented wizard, you probably already know that the most effective weapon against dementors so far is a Patronus, which is basically a manifestation of good will and happiness. And Hermione wants to estimate the happiness in some spells, because she thinks the happier a spell is, the more effective it will be against dementors. Clever, isn’t she?! That’s where the Mirror of Erised comes in. When the happiest man on Earth looks into the mirror, the mirror shows back only himself in reflection. On the golden frame of the mirror, a writing is inscribed - "erised straeh ruoy tub ecaf ruoy ton wohs i". Hermione noted that when this text is reversed and the spaces are rearranged, it becomes "i show not your face but your hearts desire"!

So from these clues of the mirror, Hermione figured, if a spell is the same when it is reflected, it is a happy spell and thus it will work effectively on dementors, and here, reflection actually means reversal i.e. a string is happy when it is the same after reversal i.e. it is palindromic.
Now, Hermione knows a very strong spell, and so does Harry. Hermione thinks any new spell that is common to both of these strong spells will also be considerably strong. The new spell needs to be happy too of course, to work better on dementors. Using a technique she learned in RUET (Rajshahi University of Enchantment and Transfiguration), Hermione has found strings (string S1 and string S2) that are equivalent to the strong spells Harry and she know. Now, they just need to find the longest happy substring that is common in both S1 and S2, which termed as LCHS.

Since Harry and Hermione are quite busy with the other parts of their research, for assistance, they have sent for you, the best wizard of RUET. Can you help them out by finding the length of the LCHS of S1 and S2?


The input will contain two strings S1 and S2, each string in a single line, 1 ≤ |Si| ≤ 105 . Here |Si| means the length of the i-th string Si .

Remember S1 and S2 will contain lowercase English alphabets only.


Print a single integer - length of the LCHS of S1 and S2.





    52% Solution Ratio

    YouKnowWhoEarliest, Aug '19

    AUST_OnslaughtFastest, 0.0s

    ShadowMeLightest, 3.7 MB

    TahseenShortest, 1031B


    Login to submit


    Approach 1: Binary Search and Hashing Approach 2: Palindromic Tree, DFS

    Toph uses cookies. By continuing you agree to our Cookie Policy.