# Zigzag String

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 text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR"
```
**Example 2 : **
ABCD, 2 can be written as

```A....C
...B....D
```
and hence the answer would be ACBD.

Method:

We notice that for the first row, the gap between words is 2 * (B - 1), in the example, if B = 5, then it's 8. For the second row, the gap is 6,2,6,2,6,2, etc.. For the third row, it's 4,4,4,4,4... Fourth row: 2,6,2,6,2,6. Fifth row: 8,8,8,8,8,8.

Solution:

Time: O(n)
Space: O(1)

```public class Solution {
public String convert(String A, int B) {
if (B == 1) return A;
StringBuilder sb = new StringBuilder();
char[] arr = A.toCharArray();
int cap = 2 * (B - 1);
int gap = cap;
boolean flip = false;
int start = 0;
int i = 0;
while (sb.length() < A.length()) {
sb.append(arr[i]);
if (i + gap <= A.length() - 1) {
i += gap;
} else {
i = ++ start;
flip = false;
}
int nextGap = cap - ( (start * 2) % cap );
if (start != 0 && start != B - 1) {
if (!flip) {
gap = nextGap;
flip = true;
} else {
gap = cap - nextGap;
flip = false;
}
} else {
gap = nextGap;
}
}
return sb.toString();
}
}```

```class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder sb = new StringBuilder();
int maxGap = 2 * (numRows - 1);
int gap = maxGap;
int start = 0;
int i = 0;
boolean flip = false;
while (sb.length() < s.length()) {
sb.append(s.charAt(i));
if (i + gap < s.length()) {
i += gap;
} else {
start ++;
i = start;
flip = false;
}
int nextGap = maxGap - ( 2 * start ) % maxGap;
if (start != 0 && start != numRows - 1) {
if (flip) {
gap = maxGap - nextGap;
flip = false;
} else {
gap = nextGap;
flip = true;
}
} else {
gap = nextGap;
}
}
return sb.toString();
}
}```