Zig-Zag String

Easy
0/40
Average time to solve is 15m
32 upvotes
Asked in companies
FacebookAppleOYO

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’).
Detailed explanation ( Input/output format, Notes, Images )
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

Sample Input 1:

2
7 3
ABCDEFG
5 2
NINJA

Sample Output 1:

AEBDFCG
NNAIJ

Explanation For Sample Input 1:

Test Case 1:

sample1

There are three rows (‘m = 3’) in the zig-zag pattern. Row one contains ‘AE’, row two contains ‘BDF’, and row three contains ‘CG’. After concatenating the three rows, we get the string ‘AEBDFCG’. So, the answer is ‘AEBDFCG’.

Test Case 2:

sample2

There are two rows (‘m = 2’) in the zig-zag pattern. Row one contains ‘NNA’, and row two contains ‘IJ’. After concatenating the two rows, we get the string ‘NNAIJ’. So, the answer is ‘NNAIJ’.

Sample Input 2:

2
4 2
PQRS
6 6
ZIGZAG

Sample Output 2:

PRQS
ZIGZAG
Hint

Observe that for every character in ‘str’ the next character is either one row below or one row above.

Approaches (2)
Iteration

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’.

 

  1. Create an array of strings named ‘arr’ of size ‘m’.
  2. 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.
  3. 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’.
  4. Initialize ‘result’ as an empty string, use it to store the answer.
  5. Run a loop where ‘i’ ranges from 0 to ‘m-1’. Append ‘result’ with the string at ‘arr[i]’.
  6. Returns ‘result’ as the answer.
Time Complexity

O(N), where ‘N’ is the length of the string ‘STR’. 

 

We run two loops, one from 0 to ‘N’ and the other from 0 to ‘M’. The first loop runs for ‘O(N)’ time. The second loop appends a total of ‘N’ elements at the end of the ‘result’ string, thus taking ‘O(N)’ time. Therefore, the time complexity is ‘O(N)’.

Space Complexity

O(N), where ‘N’ is the length of the string ‘STR’.

 

We create an array of strings ‘arr’, of size ‘M’. The array index ‘arr[i]’ stores the string at a row ‘i’ in the zig-zag pattern of ‘STR’. If we combine all strings in ‘arr’, the resultant string’s length is equal to the length of ‘STR’, i.e., ‘N’. Hence, the number of characters stored in ‘arr’ is equal to ‘N’.

Code Solution
(100% EXP penalty)
Zig-Zag String
Full screen
Console