2039B.md (1830B)
1 Source: https://codeforces.com/problemset/problem/2039/B 2 3 B. Shohag Loves Strings 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 For a string $p$, let $f(p)$ be the number of distinct non-empty substrings$^{\text{∗}}$ of $p$. 22 23 Shohag has a string $s$. Help him find a non-empty string $p$ such that $p$ is a substring of $s$ and $f(p)$ is even or state that no such string exists. 24 25 $^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The first and only line of each test case contains a string $s$ ($1 \le |s| \le 10^5$) consisting of lowercase English letters. 32 33 It is guaranteed that the sum of the length of $s$ over all test cases doesn't exceed $3 \cdot 10^5$. 34 35 Output 36 37 For each test case, print a non-empty string that satisfies the conditions mentioned in the statement, or $-1$ if no such string exists. If there are multiple solutions, output any. 38 39 Example 40 41 Input 42 43 ``` 44 5 45 46 dcabaac 47 48 a 49 50 youknowwho 51 52 codeforces 53 54 bangladesh 55 ``` 56 57 Output 58 59 ``` 60 abaa 61 -1 62 youknowwho 63 eforce 64 bang 65 ``` 66 67 Note 68 69 In the first test case, we can set $p = $ abaa because it is a substring of $s$ and the distinct non-empty substrings of $p$ are a, b, aa, ab, ba, aba, baa and abaa, so it has a total of $8$ distinct substrings which is even. 70 71 In the second test case, we can only set $p = $ a but it has one distinct non-empty substring but this number is odd, so not valid. 72 73 In the third test case, the whole string contains $52$ distinct non-empty substrings, so the string itself is a valid solution.