Zig-Zag Conversion
You are given a string ‘S’ and an integer ‘ROW’, convert the row into a zig-zag pattern with rows equal to ‘ROW’ and output it row-wise. You may refer to the example below to better understand what the zig-zag pattern means.

Example :

If ‘S’ = “beaninjacoder” and ‘ROW’ = 4 Then the zig-zag pattern is: b j r e n a e a i c d n o Therefore, we will print “bjrenaeaicdno”.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows: The first line of each test case contains a string ‘S’, denoting the input string. The second line of each test case contains a single integer ‘ROW’, denoting the number of rows in the zig-zag pattern to be created.

Output Format :

For each test case, print the new string after zig-zag conversion. Output for each test case will be printed in a separate line.

Note :

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

Constraints :

1 ≤ ‘T’ ≤ 10 1 ≤ |S| ≤ 10000 1 ≤ ‘ROW’ ≤ 10000 S only contains lower case English alphabets Time limit: 1 sec

Question

Zig-Zag Conversion

You are given a string ‘S’ and an integer ‘ROW’, convert the row into a zig-zag pattern with rows equal to ‘ROW’ and output it row-wise. You may refer to the example below to better understand what the zig-zag pattern means.

Example :

If ‘S’ = “beaninjacoder” and ‘ROW’ = 4

Then the zig-zag pattern is:
b         j        r
e     n   a     e
a   i     c   d
n         o

Therefore, we will print “bjrenaeaicdno”.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a string ‘S’, denoting the input string.

The second line of each test case contains a single integer ‘ROW’, denoting the number of rows in the zig-zag pattern to be created.

Output Format :

For each test case, print the new string after zig-zag conversion.

Output for each test case will be printed in a separate line.

Note :

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

Constraints :

1 ≤ ‘T’ ≤ 10      
1 ≤ |S| ≤ 10000
1 ≤ ‘ROW’ ≤ 10000
S only contains lower case English alphabets


Time limit: 1 sec

Accepted Answer

Pattern Formation

Consider the case where the number of rows is equal to 10, and everything has a 0 based indexing. In that case, the input string's indexes form the given pattern:

Here Step-2 involves passing through the lower part of the zig-zag, and Step-1 involves passing the upper part of the zig-zag.

Using some pattern recognition we can find all the indices that lie in a particular row. Let’s say we need to find all the indices that lie in 5’th row, the first element will itself be the 5’th index and the next element can be calculated using the step-2, if curRow stores the current row number and curIdx stores the current index number then the next element will be after 2 * (|S| - 2 - curRow) + 2 indices. Further, we will apply the step-1 as we will now have to pass the upper part of the zig-zag and the next element will now lie after 2 * (curRow - 1) + 2 indices and to find the next element we will again have to apply the step-2 and the process we keep on repeating itself.

In general, we can find all the elements of each row and for a particular row, we can stop the search if the current index exceeds the length of the input string. But we need to cover the border case of the number of rows equal to one separately here, this is because of the way we have defined our pattern recognition formula above.

The steps are as follows :

Check if ‘Row’ is equal to 1, then return the input string itself, this is the border case when the zig-zag conversion would have no effect on the original string.
Initialize a variable ‘N’ equal to S.length, this variable stores the length of the input string.
Declare a string ‘zigZag’, this string will store the final answer.
Run a for loop for the variable ‘curRow’ from 0 to minimum of Row - 1 and N - 1, this is because that the number of rows will actually be used will be equal to ‘N’ if ‘N’ is less than ‘Row’, and we won’t have to handle any extra cases later on. Inside the loop:
- Initialize a variable ‘curIdx’ equal to ‘curRow’, this variable will store the information about the current index.
- Initialize a variable ‘step1’ equal to 2 * (curRow - 1) + 2.
- Initialize a variable ‘step2’ equal to 2 * (N - 2 - curRow) + 2.
- Insert the character at the curIdx’th index of the input string in the ‘zigZag’ string.
- Run a while loop till the value of ‘curIdx’ is less than N’, inside the loop:
  - Check if ‘step2’ is greater than 0, then increment the ‘curIdx’ with step2’s value, and check if the new ‘curIdx’ is less than ‘N’ and then insert the character at the curIdx’th index of the input string in the ‘zigZag’ string.
  - Now check if ‘step1’ is greater than 0, then increment the ‘curIdx’ with step1’s value, and check if the new ‘curIdx’ is less than ‘N’ and then insert the character at the curIdx’th index of the input string in the ‘zigZag’ string.
Finally, return the string ‘zigZag’.

Space Complexity: O(n)Explanation:

O( N ), where N denotes the length of the string.

Extra space is used to store the string after zig-zag conversion, the length of this string is always equal to the length of the input string.

Hence the space complexity is O( N ).

Time Complexity: O(n)Explanation:

O( N ), where N denotes the length of the string.

While searching for indices lying in each row, each index of the input string is visited exactly once. The number of indices in the input string is equal to the length of the string.

Hence the time complexity is O( N ).

Python (3.5)

'''

    Time Complexity: O( N )

    Space Complexity: O( N )



    where N denotes the length of the string.

'''





def zigzagConversion(s: str, row: int) -> str:



    # Border case.

    if (row == 1):

        return s



    #  Initialize a variable to store the length of string.

    n = len(s)



    # Declare a string to store the final answer.

    zigZag = ""



    # Iterate each row.

    for curRow in range(min(row, n)):



        # Variable to store the current index.

        curIdx = curRow



        # Initialize a variable ‘step1’.

        step1 = 2 * (curRow - 1) + 2



        # Initialize a variable ‘step2’.

        step2 = 2 * (row - curRow - 2) + 2



        # Insert the first character of the current row.

        zigZag += (s[curIdx])



        # Insert other charachters of the current row.

        while (1):



            #  Passing through the lower part of the zig-zag.

            if (step2 > 0):



                # Increment the value of 'curIdx'.

                curIdx += step2



                # Check if reached the end of this row.

                if (curIdx >= len(s)):

                    break



                # Insert the next charachter.

                zigZag += (s[curIdx])



            # Passing through the upper part of the zig-zag.

            if (step1 > 0):



                # Increment the value of 'curIdx'.

                curIdx += step1



                # Check if reached the end of this row.

                if (curIdx >= len(s)):

                    break



                # Insert the next charachter.

                zigZag += (s[curIdx])



    # Return the string after zig-zag conversion.

    return zigZag

Java (SE 1.8)

/*
    Time Complexity: O( N )
    Space Complexity: O( N )

    where N denotes the length of the string.
*/

public class Solution {
    public static String zigzagConversion(String s, int row) {
        // Border case. 
        if (row == 1) {
            return s;
        }

        // Initialize a variable to store the length of string.
        int n = s.length();

        // Declare a string to store the final answer.
        StringBuffer zigZag = new StringBuffer("");  

        // Iterate each row.    
        for (int curRow = 0; curRow < Math.min(row, n); curRow++) {

            // Variable to store the current index.
            int curIdx = curRow;

            // Initialize a variable 'step1'.
            int step1 = 2 * (curRow - 1) + 2;

            // Initialize a variable 'step2'.
            int step2 = 2 * (row - curRow - 2) + 2;

            // Insert the first character of the current row.
            zigZag.append(s.charAt(curIdx));

            // Insert other charachters of the current row.
            while (true) {

                // Passing through the lower part of the zig-zag.
                if (step2 > 0) {

                    // Increment the value of 'curIdx'.
                    curIdx += step2;

                    // Check if reached the end of this row.
                    if (curIdx >= s.length()) {
                        break;
                    }

                    // Insert the next charachter.
                    zigZag.append(s.charAt(curIdx));
                }

                // Passing through the upper part of the zig-zag.
                if (step1 > 0) {

                    // Increment the value of 'curIdx'.
                    curIdx += step1;

                    // Check if reached the end of this row.
                    if (curIdx >= s.length()) {
                        break;
                    }

                    // Insert the next charachter.
                    zigZag.append(s.charAt(curIdx));
                }
            }
        }

        String answer = zigZag.toString();

        // Return the string after zig-zag conversion.
        return answer;
    }
}

C++ (g++ 5.4)

/*

    Time Complexity: O( N )

    Space Complexity: O( N )



    where N denotes the length of the string.

*/



string zigzagConversion(string s, int row) {



    // Border case. 

    if (row == 1) {

        return s;

    }



    // Initialize a variable to store the length of string.

    int n = s.size();



    // Declare a string to store the final answer.

    string zigZag;



    // Iterate each row.    

    for (int curRow = 0; curRow < min(row, n); curRow++) {



        // Variable to store the current index.

        int curIdx = curRow;



        // Initialize a variable ‘step1’.

        int step1 = 2 * (curRow - 1) + 2;



        // Initialize a variable ‘step2’.

        int step2 = 2 * (row - curRow - 2) + 2;



        // Insert the first character of the current row.

        zigZag.push_back(s[curIdx]);



        // Insert other charachters of the current row.

        while (1) {



            // Passing through the lower part of the zig-zag.

            if (step2 > 0) {



                // Increment the value of 'curIdx'.

                curIdx += step2;



                // Check if reached the end of this row.

                if (curIdx >= s.size()) {

                    break;

                }



                // Insert the next charachter.

                zigZag.push_back(s[curIdx]);

            }



            // Passing through the upper part of the zig-zag.

            if (step1 > 0) {



                // Increment the value of 'curIdx'.

                curIdx += step1;



                // Check if reached the end of this row.

                if (curIdx >= s.size()) {

                    break;

                }



                // Insert the next charachter.

                zigZag.push_back(s[curIdx]);

            }

        }

    }



    // Return the string after zig-zag conversion.

    return zigZag;

}

You are given a string ‘S’ and an integer ‘ROW’, convert the row into a zig-zag pattern with rows equal to ‘ROW’ and output it row-wise. You may refer to the example below to better understand what the zig-zag pattern means.

Example :

Input Format :

Output Format :

Note :

Constraints :

Top Freshworks Lead Software Engineer interview questions & answers

Popular interview questions of Lead Software Engineer

Top HR questions asked in Freshworks Lead Software Engineer