MACHO - Editorial

Problem Link:



Author: Parth Trehan

Editorialist: Parth Trehan




Count the number of pairs that can be formed holes in a character and the number of pairs of non-hold characters.


Given are two strings, we need to compare the two strings on a given constraint called the “toingness”, which is nothing but the sum of pair of total holes and the pair of character that do not contain any hole.
The number of holes in a character is given below:
A-1 B-2 C-0 D-1 E-0 F-0 G-0 H-0 I-0 J-0 K-0 L-0 M-0 N-0 O-1 P-1 Q-1 R-1 S-0 T-0 U-0 V-0 W-0 X-0 Y-0 Z-0
1-0 2-0 3-0 4-1 5-0 6-1 7-0 8-2 9-1 0-1
a-1 b-1 c-0 d-1 e-1 f-0 g-1 h-0 i-0 j-0 k-0 l-0 m-0 n-0 o-1 p-1 q-1 r-0 s-0 t-0 u-0 v-0 w-0 x-0 y-0 z-0
To calculate the “toingness”, just add the total number of holes and the total number of characters without any hole. The toingness then can be calculated by formula:

toingness = (total holes)/2 + (total characters without any holes)/2

Both the strings can be compared on the basis of the given attribute.

Time complexity: O(n) where n is the length of the string with maximum length


Setter’s solution