codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.