A pair of strings R and S is called granama if each letter ‘a’ - ‘z’ is used the same number of times in both R and S. However, Chef mistakenly considers them as granama if there are no letters which are used in R but not used in S (or vice-versa).
Determine whether Chef correctly classified two strings R and S as granama or not granama.
The answer is NO if both R and S have the same set of letters and there is at least one letter which is used different number of times in R and S. Otherwise, the answer is YES.
The most intuitive way to solve this problem is to simulate both methods of classifying whether a pair of strings is granama: the correct method and Chef’s wrong method. If both methods return the same answer, output “YES”, else output “NO”.
read(R, S) if correct_method(R, S) = wrong_method(R, S): println("YES") else: println("NO")
There are several ways to implement the correct method.
- Use two tables: freqR and freqS. Populate the tables with the frequencies of letters 'a' - 'z' in R and S. The answer is "YES" if and only if the frequency of each letter is equal in both R and S.
function correct_method(R, S): for i = 0; i < length(R); i++: freqR[R[i] - 'a']++ for i = 0; i < length(S); i++: freqS[S[i] - 'a']++ res = "YES" for i = 0; i < 26; i++: if freqR[i] ≠ freqS[i]: res = "NO" return res
- Sort both R and S based on their letters. If they become equal, the answer is "YES", otherwise "NO".
Chef’s Wrong Method
Chef will consider a pair of strings as granama if they have the same set of letters. Therefore, we can use two boolean tables: usedR and usedS. For each letter in R and S, mark it as used in the corresponding table. The answer is “YES” if and only if the flag of each letter is equal in both R and S.
function wrong_method(R, S): for i = 0; i < length(R); i++: usedR[R[i] - 'a'] = true for i = 0; i < length(S); i++: freqS[S[i] - 'a'] = true res = "YES" for i = 0; i < 26; i++: if usedR[i] ≠ usedS[i]: res = "NO" return res
The above method suffices to get Accepted on this problem. However, there is a concise solution mentioned in the Quick Explanation section based on a clever observation. The proof is left as an exercise for the readers.
Will be provided soon.
Can be found here.