6. ZigZag Conversion

/**

 * 6. ZigZag Conversion

 * The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

 *

 * P   A   H   N

 * A P L S I I G

 * Y   I   R

 * And then read line by line: “PAHNAPLSIIGYIR”

 *

 * Write the code that will take a string and make this conversion given a number of rows:

 *

 * string convert(string s, int numRows);

 * Example 1:

 *

 * Input: s = “PAYPALISHIRING”, numRows = 3

 * Output: “PAHNAPLSIIGYIR”

 * Example 2:

 *

 * Input: s = “PAYPALISHIRING”, numRows = 4

 * Output: “PINALSIGYAHRPI”

 * Explanation:

 * P     I    N

 * A   L S  I G

 * Y A   H R

 * P     I

 * print characters in a string in zig zag pattern

 */

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/ZigZagConversion.java

This is a common interview question and the approach is somewhat tricky to conceptualize.

Observations:

• Output needs to be written per row
• Characters will repeat after a cycle which is determined by number of rows
  • Cycle length = 2*N-2 where N is the number of rows, 2 is multiplied by N because there are two repeats per row per cycle except for the first and last row (hence 2 is subtracted)
• First and last row will have one repeat per cycle as they are on the edge
• Rows in the middle will have two repeats per cycle  
  • One repeat is when the next cycle starts
  • The second repeat can be calculated as next repeat of the char for first row and how far this row is from the first row

Algorithm is:

• Iterate across rows so as to output characters per row
• Iterate across columns for the given row while advancing the column by cycle length per iteration
  • For the first and last row output only one char per loop since they are on edges
  • For other rows
    • output character at the given cycle for the row
    • in addition, output another character using the distance this row is from next cycle of the first row (j+cyclelen-i). “j” is current cycle iteration, add another cycle to get the index of next cycle for first row. Subtract “i” from the value because “i “ signifies the row index and hence how far this row is from the first row.

Here is the code:

public String convert(String s, int numRows) {
    if (numRows == 1) return s;
    StringBuilder ret = new StringBuilder();
    int n = s.length();
    //cycle is twice number of rows -2. every row except first and last gets two repeats
    int cycleLen = 2 * numRows - 2;
    for (int i = 0; i < numRows; i++) {
        //repeat every cycleLen
        for (int j = 0; j + i < n; j += cycleLen) {
            ret.append(s.charAt(j + i));
            if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) {
                //this repeat is for rows except first and last
                //its :  next repeat of first row which is j + cycleLen and then subtract how far
                //this row is from the first row.
                ret.append(s.charAt(j + cycleLen - i));
            }
        }
    }
    return ret.toString();
}