In-Place Interleaving of Two Strings

Question

 Given a string, e.g., str=substr1substr2, interleave the substrings substr1 and substr2 in-place. 
 This can be extended to three strings or more. For three strings str = substr1substr2substr3, interleave the sub strings to generate a unified string.

 Example

For two strings:
Given str = A1 A2 A3 B1 B2 B3, interleave  substr1= A1 A2 A3 and substr2= B1 B2 B3 in-place to obtain A1 B1 A2 B2 A3 B3.

For three strings:
A1 A2 A3 b1 B2 B3 C1 C2 C3, interleave substr1 = A1 A2 A3, substr2 = B1 B2 B3, and substr3 = C1 C2 C3, interleave to get A1 B1 C1 A2 B2 C2 A3 B3 C3

Solution Idea

 

 

 

Java Code

public class SeqInterleave {

    /**

     * @param args

     */

   

    public static void main(String[] args) {

        

        /*

         * Input

         */

        String[] strIn = {"A1","A2","A3","A4","A5", "A6", "A7","B1", "B2", "B3", "B4", "B5", "B6", "B7"};

        

        

        /*

         * We assume that the elements in the array are valid

         * The size of the array is even

         * The size of each type is half of the total array length

         */

        SeqInterleave seqObj = new SeqInterleave();

        seqObj.interleave(strIn);

        seqObj.printOutput(strIn);

    }

   

   

    public void interleave(String[] strIn)

    {

        int stringHalfLen = strIn.length/2;

        

        //start swapping from A7
       // Loop 1

        for(int i = stringHalfLen-1, j = 0; i > 0 ; i--, j++)

        {

            int exStartPoint = i;

            int exEndPoint = stringHalfLen+j;

          
           // Loop2

            for(int k = exStartPoint ; k <= exEndPoint; k=k+2)

            {

                String temp = strIn[k];

                strIn[k] = strIn[k+1];

                strIn[k+1]= temp;

            }

            printOutput(strIn);

            System.out.println();

        }

        

    }

   

    public void printOutput(String[] strIn)

    {

        for(int i = 0; i < strIn.length ; i++)

            System.out.print(strIn[i]+" ");

    }

}

Input

A1 A2 A3 A4 A5 A6 A7 B1 B2 B3 B4 B5 B6 B7

 

Execution Output Sequence

A1 A2 A3 A4 A5 A6 B1 A7 B2 B3 B4 B5 B6 B7
A1 A2 A3 A4 A5 B1 A6 B2 A7 B3 B4 B5 B6 B7
A1 A2 A3 A4 B1 A5 B2 A6 B3 A7 B4 B5 B6 B7
A1 A2 A3 B1 A4 B2 A5 B3 A6 B4 A7 B5 B6 B7
A1 A2 B1 A3 B2 A4 B3 A5 B4 A6 B5 A7 B6 B7
A1 B1 A2 B2 A3 B3 A4 B4 A5 B5 A6 B6 A7 B7 

 

Complexity

For an array of length n, it has  O( n^2) time complexity.

Loop1 has  ((n/2)-1) iterations.

In each iteration i, we perform i swappings. In each swap, two elements of the array are used.