The string “KICKSTART” can be written in a vertical zig-zag fashion in a given number of rows:

K        S        T

I    K   T   R

C        A

Reading this string line by line gives us the resultant string as “KSTIKTRCA”. 

You are given a string and the number of rows you can occupy. Write a code that returns the line by line representation of the string when it is written in the vertical zig-zag fashion in the given number of rows.

Example One

Input: INTERVIEW, 4

Output: IINVETRWE

The given string can be written in a zig-zag fashion in 4 rows as follows:

I                    I

N          V     E 

T    R           W

E

Example Two

Input: KICKSTART, 1

Output: KICKSTART

Notes

Constraints:

• 1

• 1

• The string may contain the following ASCII characters only: a..z, A..Z, 0..9

Solution

We provided one solution.

Throughout this editorial, we will refer to the input string as str and the given number of rows as num_of_rows.

1) simulate_real_process.cpp

We will maintain the contents of each line of the zig-zag pattern separately and finally, to generate our output string, we will iterate through all the lines and will keep adding the contents of those lines to our resultant string.

So, the idea is to build an array of strings of size num_of_rows (Let us call this array as lines) where lines[i] will represent the contents of the i-th line. 

Let’s say, we have been given str = “KICKSTART” and num_of_rows = 3.

Now, this string will be written in a zig-zag fashion as follows:

K         S         T

I    K    T   R

C         A

So, our lines array should look like:

lines[] = {“KST”, “IKTR”, “CA”}.

Finally, we will build our resultant string as lines[0] + lines[1] + lines[2] which will be “KSTIKTRCA” for this example. 

So, the question arises is how will we build the array lines?

The idea is quite simple and very analogous to how we manually built our result. Let us try to simulate that process. We will iterate the input string from left to right and add the characters of it one by one to the appropriate position of our lines array.

We will keep a track of the index of the string we are on as well as of the current line.

So, we need two things as of now:

● Current index of the string str. Let us call this string_index.

● Index of the row in array lines we are currently filling. Let us call this current_row. 

Also, as you might have observed, at some instances of time, we are moving downwards through the array lines while at the other instances, we are moving upwards.

Therefore, we also need to keep a track of the direction we’re moving in. That is, whether we are moving upwards or downwards.

Let us keep a Boolean variable going_down for this purpose.

Here, going_down = True will mean that we are moving down the rows and vice-versa.

Now, we are almost done and the only thing we’re left with, is to fill the array lines.

We will iterate through the entire string (ie, till string_index < string_length) and will add str[string_index] to lines[current_row]. 

After each iteration, we will update current_row = current_row + 1 if going_down = True. Else, we will update current_row = current_row - 1. 

Also, as you might have observed, we reverse our direction when we are at one of the end rows. That is, either when current_row = 0 or current_row = num_of_rows - 1. 

Now, since we are done with all the prerequisites, let us see how this approach will fill the array lines for the following example:

str = “KICKSTART”, num_of_rows = 3.

The transitions will look like:

{“K”, “”, “”} Move DOWN

{“K”, “I”, “”} Move DOWN

{“K”, “I”, “C”} Move UP

{“K”, “IK”, “C”} Move UP

{“KS”, “IK”, “C”} Move DOWN

{“KS”, “IKT”, “C”} Move DOWN

{“KS”, “IKT”, “CA”} Move UP

{“KS”, “IKTR”, “CA”} Move UP

{“KST”, “IKTR”, “CA”} Move DOWN

Finally, as pointed out before, we generate our result as:

lines[0] + lines[1] + lines[2] = “KSTIKTRCA”.

The above approach looks fine. But does it work for the case when num_of_rows is 1? No it does not. In this case, we do not have to move up and down the rows. Rather, all the work has to be done in a single row itself. So, we will have to handle this edge case separately to return the input string itself in case when num_of_rows = 1.

Time Complexity:

O(length of str).

Since we are iterating through each character in the string only once. 

Auxiliary Space Used:

O(num_of_rows  + length of str).

We created the array lines of size num_of_rows. This requires O(num_of_rows) auxiliary space. We also stored all the characters of the input string in this array. This requires O(length of str) space.

Space Complexity:

O(num_of_rows  + length of str).

For space complexity, we also include the space occupied by input and output strings. So, the space complexity of this would be O(num_of_rows + 3*(length of str)) = O(num_of_rows + length of str).

// -------- START --------

string convert_zigzag_string(string str, int num_of_rows) {
    if (num_of_rows == 1) {
        return str;
    }

    int len = str.length();

    // An array to store the content of each row.
    vector < string > lines(min(len, num_of_rows), "");

    int current_row = 0; // Keeps a track of which line we are filling.

    bool going_down = false; // Keeps a track of the direction we are moving.
    // Although we are moving down the rows initially, we have set going_down
    // to false. Reason being, we reverse the direction when we are either at the
    // top-most or bottom-most row of "lines". Since we start with the 0-th row, the direction
    // gets reversed after the first iteration itself.

    int string_index = 0; // Index of the character which we are going to add to the "lines" next.

    while (string_index < len) {
        lines[current_row] += str[string_index];
        string_index++;

        // If we are at one of the end rows, we need to reverse our direction.
        if (current_row == num_of_rows - 1 or current_row == 0) {
            going_down = !going_down;
        }

        // If we are currently moving down, the next row to fill will be the (currentRow + 1)th row.
        if (going_down) {
            current_row++;
        }

        // Else, we will fill the (currentRow - 1)th row next.
        else {
            current_row--;
        }
    }

    // Reading the zig-zag string line by line.
    string result = "";
    for (int i = 0; i < lines.size(); ++i) {
        result += lines[i];
    }

    return result;
}

// -------- END --------