15,615,448 members
1.00/5 (1 vote)
See more:
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).

What I have tried:

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!
Posted
Updated 29-Jan-23 7:58am
Patrice T 29-Jan-23 11:40am
If you want help on your code, you need to show your code.
merano99 29-Jan-23 17:19pm
str1="bacd"; str2="abcd"; // 3 changes ??
There are only 2 changes here. Introducing an additional letter does not seem to make sense and would significantly complicate the task. Would that really be part of the task? It would mean that no letters may be exchanged directly, which already occur. One would then have to introduce new letters, remember which places would still have to be changed in further runs.
Simon tIV 30-Jan-23 7:38am
how do you change "bacd" to "abcd" in less than 3 changes then?
merano99 30-Jan-23 11:23am
I had overlooked that the number of calls of the "operation" are counted, not the number of necessary swap operations.
If the "operation" is really only allowed to always replace each existing letter a in str1 with a (freely selectable) letter ß, one would have to call the operation several times and do additional work. A lookup table would also be helpful here. More runs would then be necessary when the problem occurs and additional characters would have to be managed in it.

## Solution 1

As Patrice already said, hardly anyone here will write a ready-made solution without you uploading a source code proposal.

My suggestion for the solution would be first to create a lookup table in which all necessary changes are entered. If during the creation of this table conflicts should already be noticed, one would stop with an appropriate message. In the second step you could make the changes and count them.

// edit:
The number of calls of the necessary "operation" are to be counted, thus this function is given by the task. More efficient solutions were not asked here. In particular, this function must be called several times with (freely selectable) letters that are to be replaced.

C++
```int operation(string &s, char a, char b)
{
int cnt = 0;
if (a != b) {
for (auto it = s.begin(); it != s.end(); ++it) {
if (*it == a) {
*it = b;
cnt++;
}
}
}
return cnt;
}```

A lookup table can be realized with a std::map. I used the unsorted version here and defined a separate data type for it.
C++
```template<typename Key, typename Value>
using UMap = std::unordered_map<Key, Value>;

int main()
{
string str1, str2;
UMap<char, char> m;  // create a map of (char, char) pairs
int len;

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

cout << "str1: " << str1.c_str() << "\n";
cout << "str2: " << str2.c_str() << "\n";

// insert elements
len = min(str1.length(), str2.length());
for (int i = 0; i < len; i++) {

// TODO: determine if a map contains already the value

m.emplace(str1[i], str2[i]);
}

// TODO: check overlap for every position

// change all pairs
int cnt = 0;
for (const auto& n : m) {
cnt += operation(str1, n.first, n.second);   // replace and count
}

cout << "str1: " << str1.c_str() << " -  changes: " << cnt << "\n";

return 0;
}```

Note: The code is deliberately not complete here. If you add the usual includes it can be compiled. If you add the parts marked with TODO, which should be written by yourself, the task should be solved.

v2