I'd appreciate if someone could help explain the logic behind niyaznigmatul's solution for RemoveCharacters. For your convenience, I include links for the problem statement and the solution below:
- Problem Statement: https://community.topcoder.com/stat?c=problem_statement&pm=14356
- niyaznigmatul's Submission: https://community.topcoder.com/stat?c=problem_solution&cr=22744264&rd=16798&pm=14356
Thanks in advance!
I figured out the solution approach. I'm writing a very rough idea sketch below to help remind myself of the approach in the future and help others also struggling with understanding the algorithm:
i = i_25 i_24 ... i_0 is a binary number with 26 places such that if i_k = 1, then the k-th letter (a is 0) is kept. To ensure that a particular i works, we rely on the following observation: Once we filter A and B to only include characters corresponding to the places with 1's in i, if there is a mismatch between the two resulting strings, then the f table will have a number that has a 1 in the same place as i. By contrapositive, once we check that no such case exists in the inner for loop at the bottom of the code, we can be sure that there is no mismatch.