In this series of articles, we are going to solve some different algorithms and problems, mainly through C++. The goal of the whole series is to learn together how to solve complex problems and improve our logic skills. We are going to publish our own solution to the problem. Then you can send us an e-mail or contact us on social networks to propose your own personal solution to the same problem or to let us know how we can optimize our script. If your algorithm is correct we will update the article with your solution. We will also credit you for your help.

The problem of today:

The distance p (s1, s2) between s1 and s2 is the number of positions in which the characters in these strings differ. (p(duck, dark) = 2). We have three stings s1, s2, s3 of the same lenght n and we want to find a fourth string s such that p(s, s1) + p(s, s2) + p(s, s3) is minimal
Problem from codeforces.com, click here to see the full description of the problem

OUR SOLUTION (C++)

#include <iostream>
#include <string>

using namespace std;

int main() {
    // Take the lenght of the words
    int n;
    cin >> n;

    // Three input strings 's1', 's2', 's3' and the result string 's'
    string name1, name2, name3;
    string result = "";

    // Take the strings if their lenght is not equal to zero
    if (n != 0)
        cin >> name1 >> name2 >> name3;

    // For each letter of the string
    for (int c = 0; c < n; ++c) {
        // All three not equal, choose the first character
        if (name1[c] != name2[c] && name1[c] != name3[c] && name2[c] != name3[c]) {
            result += name1[c];
        }
        
        // Character s1 = character s2 -> choose this character
        else if (name1[c] == name2[c]) {
            result += name1[c];
        }
        
        // Character s1 = character s3 -> choose this character
        else if (name1[c] == name3[c]) {
            result += name1[c];
        }
        
        // Character s2 = character s3 -> choose this character
        else if (name2[c] == name3[c]) {
            result += name2[c];
        }
        
        // Choose character from first string
        else {
            result += name1[c];
        }
    }

    // Print the result
    if (n != 0)
        cout << result << endl;

    return 0;
}

HOW IT WORKS

To minimize the expression we simply need to check if the strings have some character in common. If the answer is yes then that's the character we need to add to the string. If not we can choose one character from one of the strings (we have chosen the character from the first string in our code).

As you might notice the problem has many different possible solutions, you can choose between one of them.

// For each letter of the string
for (int c = 0; c < n; ++c) {
     // All three not equal, choose the first character
     if (name1[c] != name2[c] && name1[c] != name3[c] && name2[c] != name3[c]) {
         result += name1[c];
     }
        
     // Character s1 = character s2 -> choose this character
     else if (name1[c] == name2[c]) {
         result += name1[c];
     }
        
     // Character s1 = character s3 -> choose this character
     else if (name1[c] == name3[c]) {
         result += name1[c];
     }
        
     // Character s2 = character s3 -> choose this character
     else if (name2[c] == name3[c]) {
         result += name2[c];
     }
        
     // Choose character from first string
     else {
         result += name1[c];
     }
}

EXAMPLE

s1 = 'needle
s2 = 'turkey'
s3 = 'bottle'

First character: n != t != b so we can choose one of this three letters (N).
Second character: e != u != o so we can choose one of this three letters (E).
Third character: e != r != t so we can choose one of this three letters (E).
Fourth character: d != k != t so we can choose one of this three letters (D).
Fifth character: l != e && l == l so we must choose L (L).
Sixth character: e != y && e == e so we must choose E (E).

The solution are the strings that have the first four characters from one of the three strings, the last two must be L and E.

TURTLE
p (turtle, needle) = 4
p (turtle, turkey) = 3
p (turtle, bottle) = 3
The total minimum result is 10!


NEWSLETTER

Do not lose our new articles! Sign up to our newsletter to receive one and only one email every time a new article is online. You will be able to unsubscribe to the service later if you want. What are you waiting for?

Sandro Maglione
Designer / Developer

I really love to share all the secrets and the tricks, which I learned surfing on the web or studing on my own, with some articles or tutorial online. I believe that through coding you can create a real piece of art by using only your imagination and your skills.