Hi, phu1ku, you are right. Since we need to copy those intervals into a new vector (or equivalently, erase them in the original vector), this additional operations can take O(n) time.

public String convert(String s, int nRows) {
if (s.length() == 0 || nRows <=1) return s;
boolean flag = true;
int state = 0;
StringBuilder[] sbs = new StringBuilder[nRows];
for (int i = 0; i < nRows; i++)
sbs[i] = new StringBuilder();
for (int i = 0; i < s.length(); i++){
sbs[state].append(s.charAt(i));
if ((state == nRows - 1 && flag) || (state == 0 && !flag))
flag = !flag;
state = getNext(state,flag);
}
for (int i =1; i < nRows; i++){
sbs[0].append(sbs[i]);
}
return sbs[0].toString();
}
private int getNext(int state, boolean flag){
return flag ? state +1 : state - 1;
}