Reverse String

Problem Statement

Given an input string, reverse it in place and retain the whitespace positions as is.

For example: “xm l” =>”lm x”

Another example could be “xml json” => “nos jlmx”

Approach

• Convert the String to character array and maintain 2 pointers (start ,end) where start = 0 and end = string.length()-1;
• Move both the pointers simultaneously and check
• If the charAt(start) = ‘ ‘ then increment the start pointer only.
• If charAt(end) = ‘ ‘ then decrement the end pointer only
• If both charAt(start) and charAt(end) = ‘ ‘ then increment start and decrement end pointer.
• Repeat the above steps until start < end.

Run Time Complexity

Run time Complexity is O(n) because we iterate through each character in the String.

Code

public class Test {
public static void main(String[] args) {
        System.out.println(convertToString(reverseInPlace("xm l")));
        System.out.println(reverseInPlace("xml json"));
    }
/**
     * Reverse the characters in a String while retaining the white space positions
     * @param input
     * @return character array containing the reversed characters
     */
    static char[] reverseInPlace(String input){
        if (input.length() < 1){
            return input.toCharArray();
        }
        char[] output = input.toCharArray();
int start = 0;
        int end = input.length()-1;
while (start < end){
            if (output[start] == ' '){
                start++;
            }else if (output[end] == ' '){
                end--;
            }else if (output[start] == ' ' && output[end] == ' '){
                start++;
                end--;
            }else {
                char temp = output[start];
                output[start] = output[end];
                output[end] = temp;
                start++;
                end--;
            }
        }return output;
    }
/**
     * Convert a Character array to String
     * @param output character array containing reversed characters
     * @return final resulting String
     */
    static String convertToString(char[] output){
        StringBuilder builder = new StringBuilder();
        for (char c: output){
            builder.append(""+c);
        }
        return builder.toString();
    }
}