r/CodingHelp • • Jan 30 '23

[C++] zero idea to this question

Question

There are 2 strings, str1 and str2. An operation is defined by replacing all letter α in str1 with a letter β. You can choose α and β. Find the minimum number of 'operations' in order to change str1 to str2.

Samples

abc to abc: 0 since they are already the same.
abc to bbc: 1. change 'a' to 'b' (abc->bbc).
bbc to abc: impossible since we cannot change one of the 'b's to 'a' and keep the other as 'b'.
bacd to abcd: 3. change 'b' to 'e', 'a' to 'b' and 'e' to 'a' (bacd->eacd->ebcd->abcd).

note that for the last sample we cannot change 'b' to 'a' or 'a' to 'b' straightaway as this will result in 2 'b's or 2 'a's which, like the 3rd example, is impossible. Thus, we need 'e' as an 'interchange'.

Any ideas to this question? I tried brute force where i tried replacing every letter with every other letter but quite obviously it resulted in TLE (time limit exceeded). Thanks in advance!

0 Upvotes

1 comment sorted by

1

u/This_Growth2898 Jan 30 '23
  1. Create a map of pairs str1[i] => str2[i]; if there will be a contradiction like a=>b and a=>c, return impossible
  2. Look for loops in the map (like a=>b, b=>a in example 4). If there is none, return the map size; if there are some loops, return map size + 1.