### PROBLEM LINK:

**Author:** Prateek Gupta

**Tester:** Roman Furko

**Translators:** Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Kevin Atienza

### DIFFICULTY:

Simple

### PREREQUISITES:

String processing

### PROBLEM:

Given a string S, can you remove at most one character so that the remaining string is a **double string**? A double string is a string of the form W + W for some non-empty string W.

### QUICK EXPLANATION:

The answer is `YES`

iff |S| \ge 2 and one of the following is true:

- The first \lfloor \frac{|S|}{2} \rfloor characters is a subsequence of the last \lceil \frac{|S|}{2} \rceil characters, or
- The last \lfloor \frac{|S|}{2} \rfloor characters is a subsequence of the first \lceil \frac{|S|}{2} \rceil characters.

### EXPLANATION:

# Subtask 1

Let’s first try using the simplest solution possible: Try all possible characters to remove (possibly none), and see whether any resulting string is a double string. There are only |S|+1 cases to try, because there are only |S| locations to remove a character from, plus 1 for the “*do nothing*” scenario. For this to work, we need code that checks whether a string is a double string. Here’s a pseudocode that does that:

```
def is_double_string(s):
n = s.length
if n == 0 or n % 2 != 0:
return false
h = n / 2
for i = 0..h-1:
if s[i] != s[i+h]:
return false
return true
```

(*Note:* We also return `false`

when `n == 0`

because W must be nonempty from the definition!)

With this function, we can now answer a single test case by trying all |S|+1 cases. The following is a pseudocode for this:

```
def solve(s):
n = s.length
good = is_double_string(s)
if not good:
for i = 0..n-1:
let t be s with the i'th character removed
if is_double_string(t):
good = true
break
print (if good then 'YES' else 'NO')
```

Unfortunately, checking whether a string is a double string takes O(|S|) time, so this runs in (|S|+1)O(|S|) = O(|S|^2) time, too slow for the second subtask.

# Subtask 2

Here are a few observations that will help us find a faster solution:

- Double strings are of even length, and
- Removing a letter from a string changes its parity.

This gives us the following clues on what we must do:

- If |S| is even, then we must not remove any letter.
- If |S| is odd, then we must remove exactly one letter.

In the first case, since we can’t remove any character, we simply need to check whether S is already a double string to begin with. This takes O(|S|) time so we’re good.

In the second case, we still have a problem because we don’t know which letter to remove. However, we can use the fact that in a double string, the first half is the same as the second half (by definition). Since we can only remove one character to turn S into a double string, the first “half” of S must already be nearly the same as the second “half” to begin with. (The word “half” here is a bit ambiguous because |S| is odd, but you sorta get the idea.) Specifically, the first and second “halves” must differ from each other by exactly one **deletion**. This means that the shorter “half” must be a **subsequence** of the longer “half”. Thus, we have reduced the problem to simply checking whether some string is a subsequence of another string!

Now, we still have a problem because we don’t know which “half” must be the shorter one. But there are only two possibilities to check (either the first or second half is the shorter one), so it’s no problem.

Finally, how do we quickly check whether some string, say A, is a subsequence of another string, say B? A simple greedy algorithm such as the following will do:

```
def is_subsequence(a,b):
j = 0
for i in 0..a.length-1:
// find where a[i] appears in b[j..]
while j < b.length and a[i] != b[j]:
j++
if j == b.length:
return false
j++ // "consume" b[j]
return true
```

This code runs in O(|A| + |B|) time, and since in our case |A| + |B| = |S|, and there are only two cases to check, our algorithm runs in 2\cdot O(|S|) = O(|S|).

To summarize, here is our algorithm:

```
def solve(s):
n = s.length
good = false
if n % 2 == 0:
good = is_double_string(s)
else if n > 1: // n == 1 is bad
h = n / 2
good = is_subsequence(s[0..h-1], s[h..n-1]) or is_subsequence(s[h+1..n-1], s[0..h])
print (if good then 'YES' else 'NO')
```

### Time Complexity:

O(|S|)