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:
Alice wanted to name an algorithm S_A, Bob wanted to name it S_B.
Each person will be happy only if the algorithm’s name doesn’t include any character from the name the other person wanted.
Is there a way to make both people happy?
EXPLANATION:
For both people to be happy, the name chosen should have nothing in common with both S_A and S_B.
This is only possible if, among the letters 'a'
to 'z'
, at least one of them doesn’t appear at all - neither in S_A, nor in S_B.
If there’s at least one such letter, simply choosing that letter to be the name will make both Alice and Bob happy.
So, the solution is to just check for each letter from 'a'
to 'z'
whether it appears in either S_A or S_B.
If any letter is not present in both strings, the answer is Yes
, otherwise it’s No
.
TIME COMPLEXITY:
\mathcal{O}(N+M) per testcase.
CODE:
Editorialist's code (PyPy3)
alphabet = 'qwertyuiopasdfghjklzxcvbnm'
for _ in range(int(input())):
n, m = map(int, input().split())
sa = input()
sb = input()
ans = 'No'
for c in alphabet:
if c not in sa and c not in sb:
ans = 'Yes'
print(ans)