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:

One swap on a string is performed in this way: Assuming 1 indexing, the i'th letter from the end is inserted between i'th and (i+1)'th letter from the starting. You have a string S on which we have performed K swaps. You need to find the original string.

Problem from hackerearth.com

OUR SOLUTION (C++)

#include 
#include 

using namespace std;

// The swap function
string swapString(string input) {
    // Copy the original string
    string ret = input;

    // Two indexes a and b
    int a = input.size() - 1;
    int b = 0;

    // Swap the string through a for cycle
    for (int i = 0; i < input.size(); ++i) {
        if (i % 2 == 0) {
            ret[b] = input[i];
            ++b;
        }
        else {
            ret[a] = input[i];
            --a;
        }
    }

    // Return the swapped string
    return ret;
}


int main() {
    // Get the input data
    string input;
    int swaps;
    cin >> swaps;
    cin >> input;

    // Count how many swaps before the string turns back as it was
    // We perform the first swap call outside (counting = 1)
    int counting = 1;
    string backup = input;
    input = swapString(input);

    // While function to count
    while(input != backup) {
        input = swapString(input);
        counting++;
    }

    // Reduce the swap value through modulo function
    swaps = swaps % counting;

    // Find out the solution
    for (int s = 0; s < swaps; ++s) {
        input = swapString(input);
    }

    // Print the solution
    cout << input << endl;

    return 0;
}

HOW IT WORKS

We have developed a specific function to swap the character in the given string.

// The swap function
string swapString(string input) {
    // Copy the original string
    string ret = input;

    // Two indexes a and b
    int a = input.size() - 1;
    int b = 0;

    // Swap the string through a for cycle
    for (int i = 0; i < input.size(); ++i) {
        if (i % 2 == 0) {
            ret[b] = input[i];
            ++b;
        }
        else {
            ret[a] = input[i];
            --a;
        }
    }

    // Return the swapped string
    return ret;
}

We make a copy of the original input string and we initialize two index ints: a, which starts from the end; b, which starts from 0. Then for each character, we check if it is at an even position. If so, we add at index b this character to the string and we increment the index b. If is odd we add at index a and we decrement it.

 

Then we need to reduce the number of times we call the swapString function. We know that if we repeatedly swap the string at some point it will turn back as it was at the start. We use this knowledge to drastically reduce the variable swap.

// Count how many swaps before the string turns back as it was
    
    // We perform the first swap call outside (counting = 1)
    int counting = 1;
    string backup = input;
    input = swapString(input);

    // While function to count
    while(input != backup) {
        input = swapString(input);
        counting++;
    }

    // Reduce the swap value through modulo function
    swaps = swaps % counting;



We simply need to count how many times we need to call the swapString function before the string becomes the same as it started (through the ‘counting’ variable). Then we use the % (modulo) operator to drop down the value of swap. Finally, we swap the input string a number swap of times. In such way, we can find out which was the real string and solve the problem.

// Find out the solution
    
    for (int s = 0; s < swaps; ++s) {
        input = swapString(input);
    }

    // Print the solution
    cout << input << endl;