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 1^st row. We repeat this pattern until the string ends.
2) As we can see pattern repeats once it reaches back to 1^st 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 1^st row contains 1^st 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 i^th
row contains i^th and i^th 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 i.e. 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 1^st row: We print 1^st element of each repetition string.

See Graphic-1 Above

Hence we print ecr.

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

See Graphic-2 Above

Hence we print xtopom.

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

See Graphic-3 Above

Hence we print prdrga.

For 4^th row: We print 4^th 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.