Last Updated: 2 Mar, 2021

Zig-Zag String

Easy

Asked in companies

Solve now

Problem statement

You are given a string ‘STR’ of size ‘N’ and an integer ‘M’ (the number of rows in the zig-zag pattern of ‘STR’). Your task is to return the string formed by concatenating all ‘M’ rows when string ‘STR’ is written in a row-wise zig-zag pattern.

Example:

N = 12, M = 3 and STR = ‘CODINGNINJAS’

example

There are three rows (‘M = 3’) in the zig-zag pattern. Row one contains ‘CNN’, row two contains ‘OIGIJS’, and row three contains ‘DNA’. After concatenating the three rows, we get the string ‘CNNOIGIJSDNA’. So, the answer is ‘CNNOIGIJSDNA’.

Note:

1. The string ‘STR’ consists of capital letters only (i.e., characters from ‘A-Z’).

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the size of string ‘STR’ and the number of rows in the zig-zag pattern, respectively.

The second line of each test case contains a string ‘STR’.

Output format:

For each test case, return the string formed by concatenating all ‘M’ rows when string ‘STR’ is written in a zig-zag pattern.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function

Constraints:

1 <= T <= 10^2
1 <= N <= 10^3
1 <= M <= N
‘STR’ contains only ‘A-Z’ characters.

Time Limit: 1 second

Solve now

Approaches

01 Approach

Create an array ‘arr’ of size ‘m’, use the array index ‘arr[i]’ to store the string at row ‘i’. Traverse the string ‘str’, identify the character’s row in the current iteration, and append that character to its corresponding row/index in ‘arr’.

Create an array of strings named ‘arr’ of size ‘m’.
Initialize variable ‘curRow’ with value 0 and ‘move’ with value 1. Use ‘curRow’ to identify the character’s row in the current iteration and ‘move’ to decide if we have to move down or up in rows.
Run a loop where ‘i’ ranges from 0 to ‘n-1’.
- Append the string at ‘arr[curRow]’ with the character at ‘str[i]’.
- If ‘curRow’ is equal to 0, then ‘move = 1’. Else if ‘curRow’ is equal to ‘m-1’, then ‘move = -1’.
- Compute ‘curRow += move’.
Initialize ‘result’ as an empty string, use it to store the answer.
Run a loop where ‘i’ ranges from 0 to ‘m-1’. Append ‘result’ with the string at ‘arr[i]’.
Returns ‘result’ as the answer.

Solve now

02 Approach

We observe that for the first and last row, their index is always incremented by a value of ‘2*(m - 1)’. Let ‘curRow’ be the index of the current row. For the middle rows, if we have to move in the upward direction (i.e., through the last row to the next character in that row), then the index is incremented by a value of ‘2*(m - curRow - 1)’. For the downward direction (i.e., through the first row), the index is incremented by a value of ‘2*(curRow)’. Iterate over each row and append its characters to the answer/output string.

Initialize ‘result’ as an empty string, use it to store the answer.
Run a loop where ‘curRow’ ranges from 0 to ‘m-1’.
- Initialize variable ‘pos’ with value ‘curRow’. Use it to store the position of the current row’s character in ‘str’.
- Initialize variable ‘move’ with the value true. Use it to decide if we have to move up (true) or down (false) in rows.
- Run a loop until ‘pos’ is less than ‘n’.
  - Append the string ‘result’ with the character at ‘str[pos]’.
  - If (‘curRow’ is equal to 0) or (‘curRow’ is equal to ‘m-1), then ‘pos = pos + 2*(m-1)’.
  - Else do the following.
    - If ‘move’ is equal to true, then ‘pos = pos + 2*(m - curRow - 1)’. Else, ‘pos =pos + 2*curRow’.
    - ‘move = (move XOR true)’. Taking ‘xor’ with ‘true’ toggles the boolean value of ‘move’, i.e., if ‘move’ is true, make it false, or if it’s false, make it true.
Return the ‘result’ as the answer.

Solve now