Longest Decreasing Suffix

Interview

Time limit1sMemory limit128 MB

Summary
For each string, print its longest suffix whose characters strictly decrease from left to right.
Level

Easy3 of 10

Topics
String, Implementation, Greedy, Two pointers
Solved
No attempts yet

Problem

Sam has found a possible communication pathway to the outside world, apparently left open by Clu, but he needs the correct password to check whether it still works. Clu cannot remember the passwords to the millions of gates in the Grid, so he usually writes them down somewhere nearby. He never writes a password down directly, though: he encodes it inside several strings written on the wall next to the gate. The first step in decoding the password is to find the longest decreasing suffix (LDS) of every string on the wall. Sam can handle the rest, but he needs your help with this first step.

A decreasing suffix of a string is a suffix in which each character is strictly larger than the character that follows it. The LDS of a string is the longest such suffix. For example, the LDS of abcdbca is ca, and the LDS of abcdljksdflkjzfcba is zfcba.

Input

The first line contains the number of test cases (≤50\le 50). Each of the following lines contains one input string of length <100< 100. Every input string consists only of lowercase letters a through z.

Output

For each test case, find the longest decreasing suffix of the input string and print one line in the following format:

The longest decreasing suffix of <string> is <suffix>

where <string> is the input string and <suffix> is its LDS.

Examples1

  1. Example 1

    Input
    3
abcdbca
abcdljksdflkjzfcba
qlpxosmpzygb
    Expected output
    The longest decreasing suffix of abcdbca is ca
The longest decreasing suffix of abcdljksdflkjzfcba is zfcba
The longest decreasing suffix of qlpxosmpzygb is zygb