FBMATCH - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given a string S, is it possible to rearrange it so that its first and last characters are equal?

EXPLANATION:

Since N \ge 2, for the first and last characters of S to be the same, S must certainly have some repeated character.

Now,

  • If S contains a repeated character, it’s always possible to form a valid rearrangement.
    For example, if ch denotes the repeated character, we can place one copy of ch at the start, one copy at the end, and then everything else in the middle however we like.
  • If S doesn’t contain repeated characters, it’s of course impossible to make the first and last characters of S equal.

So, the solution is to print "Yes" if S contains repeated characters, and "No" otherwise.

Checking for repeated characters can be done easily enough in quadratic time, by just comparing each pair of characters in S.

Faster solutions exist but were not needed for this problem.

TIME COMPLEXITY:

\mathcal{O}(N^2) (or better) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    ans = 'No'
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]: ans = 'Yes'
    print(ans)