Intuition
If we want to output the result by reading line by line, we need to know the index of the each character. So how to find the specific index sequence of the characters which are read line by line is what we focus on mainly.
Algorithm
Now we will try to resolve the problem as follow:
Firstly, we get the string s
, such as "ABCDEFGHIJKLMNO...", and the three row n
s, each equals 3
, 4
and 5
, as shown below:
 n = 3
A E I
B D F H J
C G K
 n = 4
A G M
B F H L N
C E I K O
D J P
 n = 5
A I Q
B H J P R
C G K O S
D F L N T
E M U
Secondly, we need to find the index sequence while reading line by line. Obviously, the indexes of the first line are what as follow:

0, 4, 8
forn = 3
; 
0, 6, 12
forn = 4
; 
0, 8, 16
forn = 5
.
Because:

For the
n = 3
case, the index of theA
character equals0
,E
equals4
,I
equals8
; 
For the
n = 4
case, the index of theA
character equals0
,G
equals6
,M
equals12
; 
For the
n = 5
case, the index of theA
character equals0
,I
equals8
,Q
equals16
;
Now, we could get the conclusion that for the first line, the distance of numbers adjacent to each other is 2(n 1)
. So the index for the k
th(k = 0, 1, 2...) element of the i
th line could be expressed by expression that 2 * k (n  1) + i
Then, we could also get the same conclusion for the n
th line, because the n
th line is similar to the 0
th line.
Then, for the other lines(the 1
th to the n  1
th lines)， the difference between the 0
th or n
th line case is that there is one more character, and the indexes of those are shown as follow:
For the n = 4
case

The
2
th line, theF
character's index equals5
,L
equals11
; 
The
3
th line, theE
character's index equals4
,K
equals10
;
So we could find the one more
character's index is 2 * i
(i
is the current line number, such as 0
, 1
, 2
, 3
...) less then the next number's.
Now, we could get the conclusion that for the 1
th to n  1
th lines, the index for the k
th(k = 0, 1, 2...) element of the i
th line could be expressed by expression that:
 for the k % 2 == 0 case, the is similar to the
0
th orn
th line, so the index isk * (n  1) + i
 for the k % 2 != 0 case, the index is
2 * i
less then the next element's. The next element's index is(k + 1) * (n  1) + i
, so the index of the current character which is before the next element is(k + 1) * (n  1) + i  2 * i
, we get the expression that(k + 1) * (n  1)  i
;
Finally, the index of the characters which are read line by line c_i
can be expressed as follow:
if (i == 0  i == n  1) {
c_i = 2 * k * (n  1) + i;
} else {
c_i = (k % 2 == 0) ? k * (n  1) + i : (k + 1) * (n  1)  i;
}
C++
public class Solution {
public string convert(string s, int n) {
if (n == 1) return s;
int l = s.length(), k = 0, c_i = 0;
string r_s = "";
for (int i = 0; i < n; ++i) {
while(true) {
if (i == 0  i == n  1) c_i = 2 * k * (n  1) + i;
else c_i = (k % 2 == 0) ? k * (n  1) + i : (k + 1) * (n  1)  i;
if (c_i >= l) break;
r_s.append(s, c_i, 1);
++k;
}
k = 0;
}
return r_s;
}
}
Complexity Analysis
 Time complexity : O(n). The n is the length of the original string.
To calculate all the characters' index, we need to scan all of them. Thus, it costs O(n) time.
 Space complexity : O(n). The extra space required for storing the characters in String as well as returning them.