using System;

using System.Linq;

using System.Collections.Generic;

using System.Text;

​

/*

​

****************This is optimized Solution *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/26141/assignment/problems/190?navref=cl_tt_nv]

Problem Description

​

You are given a string A of size N.

​

Return the string A after reversing the string word by word.

​

NOTE:

​

A sequence of non-space characters constitutes a word.

Your reversed string should not contain leading or trailing spaces, even if it is present in the input string.

If there are multiple spaces between words, reduce them to a single space in the reversed string.

​

​

Problem Constraints

1 <= N <= 3 * 105

​

​

​

Input Format

The only argument given is string A.

​

​

​

Output Format

Return the string A after reversing the string word by word.

​

​

​

Example Input

Input 1:

    A = "the sky is blue"

Input 2:

    A = "this is ib"

​

​

Example Output

Output 1:

    "blue is sky the"

Output 2:

    "ib is this"    

​

​

Example Explanation

Explanation 1:

    We reverse the string word by word so the string becomes "the sky is blue".

Explanation 2:

    We reverse the string word by word so the string becomes "this is ib".

*/                  

public class Program

{

    private static string ReverseString(string chunkString){

        int strLength = chunkString.Length;

        StringBuilder tmpSB = new StringBuilder();

        for(var i = strLength - 1; i >= 0; i--){

             tmpSB.Append(chunkString[i]);

        }

        return tmpSB.ToString();

    }

    private static string Solve(string A)

    {

        int strLength = A.Length;

        StringBuilder reversedString = new StringBuilder();

        //First: Reverse the string completely

        string fullReverseStr = Program.ReverseString(A);

        //Step 2: Reverse the word itself by finding a splitter

        StringBuilder chunkSB = new StringBuilder();

        for(var j = 0; j < strLength; j++){

            if(j == 0 && fullReverseStr[j] == ' ') { 

                fullReverseStr.Remove(0, 1);

            }else if(fullReverseStr[j] == ' '){

                //Call Reverse again

                string tmpRes = Program.ReverseString(chunkSB.ToString());

                reversedString.Append(tmpRes);

                reversedString.Append(' ');

                chunkSB = new StringBuilder();

            }else{

                chunkSB.Append(fullReverseStr[j].ToString());

            }

        }

        if(chunkSB.Length > 0) {

            string tmpRes = Program.ReverseString(chunkSB.ToString());

            reversedString.Append(tmpRes);

        }

        return reversedString.ToString();

    }

    public static void Main()

    {

        string strToReverse = "crulgzfkif gg ombt vemmoxrgf qoddptokkz op xdq hv ";

        //string strToReverse = "the sky is blue";

        //string strToReverse = "this is ib";

        string afterReverse = Program.Solve(strToReverse);

        Console.WriteLine("After Sorting:" + afterReverse);

    }

}