Reverse string with identical spaces as in original String using Java

Question

This is interview question

Reverse string with identical spaces as in original String using Java

For example

Original String :

best in the world and is greatest and is making sure the world goes well

Output:

llew se ogd lrowe hte ru sgnikams idn at setaer gsid nad lrowe htni tseb

The code I have written is as below:

import java.util.ArrayList; import java.util.List; public class CountSpaces { public static void main(String[] args) { String st = "best in the world and is greatest and is making sure the world goes well"; String st1 = st; char[] x = st.toCharArray(); int flag = 0; List<Integer> spacePositionArray = new ArrayList<Integer>(); int len = x.length; int sub = 0; for (int i = 1; i < len; i++) { char y = x[i]; if (y == ' ') { if (flag > 0) spacePositionArray.add(i - sub); else spacePositionArray.add(i); flag++; sub++; } } st = st.replaceAll("\\s+", ""); x = st.toCharArray(); len = x.length; int k = 1; for (int i = len - 1; i >= 0; i--) { if (spacePositionArray.contains(k)) { System.out.print(x[i] + " "); } else System.out.print(x[i]); k++; } System.out.println(); System.out.println(st1); } } 

Can it be done in a much simpler which is more logical. My approach is much more brute and direct.

Kindly review

Answer 1

You can make a String directly from a character array. So

public static String reverseWithoutMovingSpaces(String text) { char[] results = text.toCharArray(); for (int left = 0, right = results.length - 1; left < right; left++, right--) { while (results[left] == ' ') { left++; if (left >= right) { return new String(results); } } while (results[right] == ' ') { right--; if (left >= right) { return new String(results); } } char temp = results[left]; results[left] = results[right]; results[right] = temp; } return new String(results); } 

Since we know the length of the intended string, we can manipulate the characters of the array directly. We don't need a List<Character> nor even a StringBuilder. We can just swap in place like this was C.

We also don't need to keep track of where the spaces are once we are past them.

This isn't a very Java solution, as it doesn't delegate to any of the library functions. But in this case, we would have to go to extra effort to make the problem delegate to library functions. It's just as easy to do the work directly.

This is something of an example of the CISC/RISC school of thought. This is a RISC solution. It uses repeated low level operations to get to the result. Other solutions use higher level operations and waste effort. For example, using insert on a StringBuilder is an expensive operation that makes those solutions quadratic (\$\mathcal{O}(n^2)\$ where \$n\$ is the number of characters in the string; the worst case being a string of only spaces).

A lot of the time that won't matter. But if this is used repeatedly for long strings, it might.

It is entirely possible that this question was chosen precisely because it encourages thinking about the actual low level operations rather than the library functions. While there are many advantages to using the library functions (e.g. more thorough testing and often better optimization), there are also times when it is better to use the low level operations.

A shorter version of the above code would be

public static String reverseWithoutMovingSpaces(String text) { char[] results = text.toCharArray(); int left = 0; int right = results.length - 1; while (left < right) { if (results[left] == ' ') { left++; } else if (results[right] == ' ') { right--; } else { char temp = results[left]; results[left] = results[right]; results[right] = temp; left++; right--; } } return new String(results); } 

This duplicates some work (repeatedly checking if left points at a space if right does) but is fewer lines of code. Fewer lines of code is easier to maintain and the duplicate work would not change the asymptotic analysis, as the loop does at most \$n\$ iterations and the work per iteration has constant bounds. Both these versions of the code are linear (\$\mathcal{O}(n)\$). In practice it might take extra time; you'd have to time and test to be sure.

Note that the contains in your original solution would make that \$\mathcal{O}(n^2)\$. Because you have to loop over the original string (which you don't actually do, so you would return incorrect (empty) output on a string of only spaces; it would be pretty fast in that case though) and call contains each time. The contains method itself has to loop over the entire ArrayList.

Answer 2

I suggest you rely on StringBuilder. That way, appending to it runs in amortized constant time.

I had in mind the following implementation:

public static String reverseWithSpaces(String text) { StringBuilder stringBuilder = new StringBuilder(text.length()); StringBuilder outputBuilder = new StringBuilder(text.length()); String[] words = text.split("\\s+"); for (String word : words) { stringBuilder.append(word); } stringBuilder.reverse(); int index = 0; for (int i = 0; i < text.length(); ++i) { char c = text.charAt(i); if (c == ' ') { outputBuilder.append(' '); } else { outputBuilder.append(stringBuilder.charAt(index++)); } } return outputBuilder.toString(); } 

Above, you first lump all the non-whitespace characters to a single string builder stringBuilder. Then, you reverse the stringBuilder. The next step is to march over the input text, and for each position index you (1) add a space, or (2) add a character (in order) from the stringBuilder.

Answer 3

Namings

First, make sure names describe the thing they name. the class CountSpaces does nothing of the sort, it reverses Strings.

st, st1 and x are all the String to reverse. If you had a method that did this, the String could be called input but original works for both cases.

stringPositionArray is a List, not an array. In any case, adding the type as a suffix is unnecessary. Just call it stringIndexes, as index is the word normally used for that number. And you only use contains() which is faster with a HashSet

Unnecessary variables

flag is only used to see if sub should be subtracted or not. It always has the same value as sub and only avoids subtracting sub when it's zero. You could simply always subtract sub.

char y = x[i] could be avoided with using x[i] on the next row. And x is unnecessary as you can use String.charAt.

len is only used once for each time it's assigned. That too could be replaced with x.length or original.length() if you use a String.

For loops can contain multiple variables, so k can be inserted in the loop declaration like

for (int i = len - 1, k = 1; i >= 0; i--, k++) 

The second loop always prints x[i], only the space is conditional. Also, always use the {}. And concat a String instead of printing each char.

So far, your main method should look like

public static void main(String[] args) { String original = "best in the world and is greatest and is making sure the world goes well"; Set<Integer> spaceIndexes = new HashSet<>(); for (int i = 1, sub = 0; i < original.length(); i++) { if (original.charAt(i) == ' ') { spaceIndexes.add(i - sub++); } } String noSpaces = original.replaceAll("\\s+", ""); String reversed = ""; for (int i = noSpaces.length() - 1, k = 1; i >= 0; i--, k++) { reversed += noSpaces.charAt(i); if(spaceIndexes.contains(k)) { reversed += " "; } } System.out.println(reversed); System.out.println(original); } 

Tools

Java has loads of tools to handle Strings and more general collections of things. StringBuilder has methods for reversing a String and inserting chars in the middle. A nice trick for getting the indexes matching some condition is using IntStream.range() and filter().

StringBuilder reversed = new StringBuilder(input.replaceAll(" ", "")).reverse(); IntStream.range(0, input.length()) .filter(i -> input.charAt(i) == ' ') .forEach(i -> reversed.insert(i, " ")); 

Avoid using indexes

Indexes can cause annoying off-by-one errors. If you can do operations on an entire array, list or stream, do so. You can potentially use Iterators to traverse things when you have more than one collection to handle.

 Iterator<Integer> reverse = new StringBuilder(original.replaceAll(" ","")) .reverse() .chars() .iterator(); String output = original .chars() .mapToObj(c -> c == ' ' ? " " : Character.toString(reverse.next())) .collect(Collectors.joining()); 

Answer 4

You don't need all that much to do this. Both the OP's solution and @coderodde's seem overworked with too many extraneous objects.

One StringBuilder is needed for the result. We also need an index into the char array from the original string, initially set to the length of the original string.

Loop over the chars in the array. If a char is space add it to the output otherwise decrement the index till you find a non-space and copy that. (I'd probably write a little method to search down the array for the next non-space, or even a class implementing Iterator, just to look clever 😉)

Done!

I don't have a development environment to hand, so I leave the actual implementation as an exercise for the reader...

Answer 5

Code should always be in functions with descriptive names. Another answer did this great, using the name reverseWithoutMovingSpaces.

This is crucial during a coding interview (the question is tagged interview-question), it helps in so many ways:

• The suitable name for the function, its parameters, with names and types, the return type of the function are all essential to understanding what you're supposed to implement exactly. Unclarified misunderstandings with an interviewer will probably hurt your score.

• It's fair to ask the interviewer to help you clarify all those details, in fact it's probably part of the test if you ask or not.

• Having a dedicated function removes a lot of noise from the code. You could have asked this code review without the class declaration and the hardcoded string values used as test data. None of that adds value to the implementation.

• Having a dedicated function makes it easy to test the implementation against different inputs.

Clarifying the function where the code will live naturally guides in a good direction, encourages to ask relevant questions, and should help you score good points.

Answer 6

If I needed to do this, I'd go with Ivo Beckers' / JollyJoker's approach, but here's another take on it, just for fun - and it might generalize to some extended version of this problem.

You could treat the input string as a kind of a control sequence (a character sequence that tells your program what to do); as you loop through it, look at the current "control character":

• if it's a space, append a space to the output
• otherwise append the next char from the reversed string (previously made free from spaces)

It would look something like this (I'm using Iterator so that I could have the more readable charsInReverse.next(), to better get the idea across, but you could just make it a String and have a charsInReverse.charAt(reverseIdx++) like in the second example below):

import java.util.*; class Main { public static void main(String args[]) { String inputString = "best in the world and is greatest and is making sure the world goes well"; // --------------------------------------------------------------------- String temp = new StringBuilder(inputString.replaceAll(" ", "")).reverse().toString(); Iterator charsInReverse = temp.chars().mapToObj(i->(char)i).iterator(); StringBuilder resultBuilder = new StringBuilder(); // use the input string as a control sequence for (char c : inputString.toCharArray()) { if (c == ' ') resultBuilder.append(' '); else resultBuilder.append(charsInReverse.next()); } String result = resultBuilder.toString(); // --------------------------------------------------------------------- // Test String expectedResult = "llew se ogd lrowe hte ru sgnikams idn at setaer gsid nad lrowe htni tseb"; System.out.println("Actual: " + result); System.out.println("Expected: " + expectedResult); System.out.println("--> " + (result.equals(expectedResult) ? "OK" : "Incorrect")); } } 

Or alternatively

 String charsInReverse = new StringBuilder(inputString.replaceAll(" ", "")).reverse().toString(); int reverseIdx = 0; char[] resultArray = new char[inputString.length()]; int[] resultIdx = new int[] { 0 }; // wrapped so that it can be changed in a lambda Runnable appendSpace = () -> { resultArray[resultIdx[0]++] = ' '; }; IntConsumer appendChar = (int c) -> { resultArray[resultIdx[0]++] = (char)c; }; // use the input string as a control sequence for (char c : inputString.toCharArray()) { if (c == ' ') appendSpace.run(); else appendChar.accept((int)charsInReverse.charAt(reverseIdx++)); } String result = new String(resultArray);