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;``````