Reverse Words In A String
You are given a string of length N. You need to reverse the string word by word. There can be multiple spaces between two words and there can be leading or trailing spaces but in the output reversed string you need to put a single space between two words, and your reversed string should not contain leading or trailing spaces.

For example :

If the given input string is " Welcome to Coding Ninjas", then you should return "Ninjas Coding to Welcome" as the reversed string has only a single space between two words and there is no leading or trailing space.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow. The first and only one of each test case contains a string that you need to reverse word by word.

Output Format :

For every test case, print the reversed string such that there should be only one space between two strings and there should not be any trailing space.

Note :

Do not print anything. It has already been taken care of. If the string data type is immutable in your language, consider using a mutable data type as an alternative.

Follow-up:

If the string data type is mutable in your language, can you solve it in place with O(1) extra space?

Constraints :

1

Question

Reverse Words In A String

You are given a string of length N. You need to reverse the string word by word. There can be multiple spaces between two words and there can be leading or trailing spaces but in the output reversed string you need to put a single space between two words, and your reversed string should not contain leading or trailing spaces.

For example :

If the given input string is "  Welcome to   Coding  Ninjas", then you should return "Ninjas Coding to Welcome" as the reversed string has only a single space between two words and there is no leading or trailing space.

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 
Then the T test cases follow.

The first and only one of each test case contains a string that you need to reverse word by word.

Output Format :

For every test case, print the reversed string such that there should be only one space between two strings and there should not be any trailing space.

Note :

Do not print anything. It has already been taken care of.

If the string data type is immutable in your language, consider using a mutable data type as an alternative.

Follow-up:

If the string data type is mutable in your language, can you solve it in place with O(1) extra space?

Constraints :

1 <= T <= 50
0 <= N <= 10^5

Time Limit: 1 sec

Accepted Answer

Approach :

1) Create a String ans to store the reversed string.
2) Initialize a variable i to 0 and iterate the whole string through a while loop.
3) Skip initial spaces by just incrementing i.
4) Create a String that will store the current word.
5) Add the currentword and space at the beginning of ans.
6) After traversing the whole string, check if the length of ans is greater than 0 then return ans after removing the last space otherwise return an empty string.

TC : O(N^2), where N = length of the string
SC : O(N)

Accepted Answer

Brute force

Create a String ans to store the reversed string.
Initialize a variable i to 0 and iterate the whole string through a while loop.
Skip initial spaces by just incrementing i.
Create a String that will store the current word.
Add the currentword and space at the beginning of ans.
After traversing the whole string, check if the length of ans is greater than 0 then return ans after removing the last space otherwise return an empty string.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the string

For storing the reversed string.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where N is the length of the string

As for every word we are attaching in front of the String.

Accepted Answer

Backward Traversal

If the string is null or empty return an empty string.
If the string is “ “ then return an empty string.
Initialize a String ans to store the reversed string.
Initialize a pointer to the end of the string and run a while loop until the pointer reaches the start of the string.
Skip multiple spaces by decreasing the pointer.
Add a space to the String ans.
Run a nested while loop to extract the current word.
Add the word in the ans.
After traversing the whole string, return the ans.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the string

For storing the reversed string.

Time Complexity: O(n)Explanation:

O(N), where N is the length of the string

As for every word we are attaching it in the String.

Top JPMorgan Chase & Co. Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in JPMorgan Chase & Co. Software Developer