Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Zigzag String from the Character on Rows

Last Updated on November 17, 2022 by Sumit Kumar

### Problem Statement (Simplified):

For a given string S and number of rows R, we have to arrange each character on rows in a vertical zigzag format, and then print values row-wise.

See original problem statement here

Can you guess the Time Complexity of this solution?

#### Test Case

Input:
1
9 3
prepbytes

Output:
pbsrpyeet

Example:
For string 'prepbytes' and '3' rows, we arrange it in the following pattern.

p.......b.......s
..r...p...y...e..
....e.......t....

Now we print this row-wise, so the answer will be 'pbsrpyeet'.

### Solving Approach :

1) To make a zigzag print, we print each character on the next row, and when row ends it goes back to 1st row. We repeat this pattern until the string ends.
2) As we can see pattern repeats once it reaches back to 1st row, So we divide the string into different parts and make a set of substrings for each repetition, each substring containing 2 x ( R - 1) characters. For the above example, the above string converts into 3 substrings that are prep, byte, and s.
3) Now we can see 1st row contains 1st element of each substring, and the last row contains a mid element of each substring.
4) For the rest of the elements, we notice every ith
row contains ith and ith element in serial pattern.
5) Now we know all the patterns, we print them in serial order from every substring keeping notice that the current element does not go beyond the size of the string.

### Example

• Lets assume string S to be ‘expertcoderprogram‘ and number of rows R be 4.
• We can arrange this in this pattern :
e . . . . . . c . . . . . r . . . . .
. x . . . . t . o . . . p . o . . . m
. . p . . r . . . d . r . . . g . a .
. . . e . . . . . . e . . . . . r . .  
• We can see in each repition pattern there are $2\times(R-1)$ i.e. $2\times(4-1)$ characters. Hence there are 6 characters in each repetition pattern.
• As length of string S is 18, so there will be total 3 repetion patterns containing 6 elements each.
• These repetions strings are ‘expert‘, ‘coderp‘ and ‘rogram‘.
• Let length of each repetition string be N.
• For every row we print:

For 1st row: We print 1st element of each repetition string.

See Graphic-1 Above

Hence we print ecr.

For 2nd row: We print 2nd and (N-2+2)th i.e. 3rd element of each repetition string.

See Graphic-2 Above

Hence we print xtopom.

For 3rd row: We print 3rd and (N-3+2)th i.e. 5th element of each repetition string.

See Graphic-3 Above

Hence we print prdrga.

For 4th row: We print 4th element of each repetition string.

See Graphic-4 Above

Hence we print eer.

### Solutions

 #include <stdio.h>

int main()
{
int test;
scanf("%d", &test);

while(test--){

char a[1001], b[1001];
scanf("%s%s", a,b);

int found = 0;

if(strlen(a)>=strlen(b)){

for(int i=0; i<=strlen(a)-strlen(b) && !found; i++){

found = 1;

for(int j = 0; j<strlen(b); j++){

if( a[i+j] != b[j] ){
found = 0;
break;
}

}
}
}

if(found == 1)
printf("YES\n");
else
printf("NO\n");

}

return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
int test;
cin>>test;

while(test--){

int N, R;
cin>>N>>R;

char a[N];
cin>>a;

int pairSize = 2*(R - 1);
if(pairSize == 0)
pairSize=1;
for(int i=0; i<=pairSize/2; i++){

for(int j=0; j<(N/pairSize)+1; j++){

int pos = i+(pairSize*j);
int revPos = (pairSize - i) + pairSize*j;
if( ((pos%pairSize)==0 || (pos+(pairSize/2))%pairSize == 0 ) && pos < N)
cout<<a[(i + pairSize*j)];
else{
if( pos < N )
cout<<a[pos];
if( revPos < N )
cout<<a[revPos];
}

}

}

cout<<endl;

}

return 0;
}


import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
public static void main(String args[]) throws IOException {

Scanner sc= new Scanner(System.in);
int test = sc.nextInt();
while(test != 0){

int N = sc.nextInt();
int R = sc.nextInt();

String a = sc.next();

int pairSize = 2*(R - 1);
if(pairSize == 0)
pairSize=1;
for(int i=0; i<=pairSize/2; i++){

for(int j=0; j<(N/pairSize)+1; j++){

int pos = i+(pairSize*j);
int revPos = (pairSize - i) + pairSize*j;
if( ((pos%pairSize)==0 || (pos+(pairSize/2))%pairSize == 0 ) && pos < N)
System.out.print(a.charAt(i + pairSize*j));
else{
if( pos < N )
System.out.print(a.charAt(pos));
if( revPos < N )
System.out.print(a.charAt(revPos));
}

}

}

System.out.println();

test--;
}

}
}


for _ in range(int(input())):
N, R = map(int,input().split())
a = list(input())
pairSize = 2*(R - 1)

if(pairSize == 0):
pairSize=1

for i in range(pairSize//2 + 1):

for j in range((N//pairSize)+1):

pos = i + (pairSize * j)
revPos = (pairSize - i) + pairSize * j

if( ((pos % pairSize) == 0 or (pos + (pairSize//2)) % pairSize == 0 ) and pos < N):
print(a[(i + pairSize*j)], end = "")

else:
if( pos < N ):
print(a[pos], end = "")

if( revPos < N ):
print(a[revPos], end = "")

print()

`

#### Space Complexity

O(1)

[forminator_quiz id="1600"]

This article tried to discuss Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.