Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Reverse a String

Problem Statement

Write a Java program that implements two methods to reverse a string: one using String methods (concatenation) and another using StringBuilder. The program should return the reversed string and compare the performance of both methods for large strings (e.g., 100,000 characters). Test the implementation with strings of varying lengths, including edge cases like empty strings and single-character strings. You can visualize this as flipping a sequence of letters, like rearranging a word written on a whiteboard, using two different tools: one that builds the result piece by piece (String) and another that efficiently manipulates the sequence (StringBuilder).

Input: A string (e.g., "hello", "", or a large string of 100,000 characters). Output: The reversed string (e.g., "olleh", "") and performance metrics (execution time in nanoseconds) for both methods. Constraints:

  • String length is between 0 and 10^6.
  • The string contains any printable ASCII characters.
  • The input is a valid string (may be empty or null). Example:
  • Input: "hello"
  • Output: "olleh"
  • Explanation: The string "hello" is reversed to "olleh".
  • Input: ""
  • Output: ""
  • Explanation: An empty string remains empty.
  • Performance Example: For a 100,000-character string, StringBuilder is significantly faster than String concatenation.

Pseudocode

FUNCTION reverseWithString(input)
    IF input is null THEN
        RETURN null
    ENDIF
    SET result to empty string
    FOR i from length of input - 1 to 0
        SET result to result + input[i]
    ENDFOR
    RETURN result
ENDFUNCTION

FUNCTION reverseWithStringBuilder(input)
    IF input is null THEN
        RETURN null
    ENDIF
    CREATE stringBuilder with input
    CALL reverse on stringBuilder
    RETURN stringBuilder as string
ENDFUNCTION

FUNCTION main()
    SET testStrings to array of strings including small, empty, and large strings
    FOR each string in testStrings
        PRINT original string
        SET startTime to current time
        CALL reverseWithString(string)
        SET stringTime to current time - startTime
        PRINT reversed string and stringTime
        SET startTime to current time
        CALL reverseWithStringBuilder(string)
        SET builderTime to current time - startTime
        PRINT reversed string and builderTime
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. String Method: a. Check if the input is null; if so, return null. b. Initialize an empty string result. c. Iterate through the input string from the last character to the first, concatenating each character to result. d. Return result.
  2. StringBuilder Method: a. Check if the input is null; if so, return null. b. Create a StringBuilder with the input string. c. Use StringBuilder’s reverse method to reverse the string. d. Return the reversed string.
  3. Performance Comparison: a. Measure execution time for both methods using System.nanoTime(). b. Test with strings of different lengths, including a large string.
  4. In the main method, test both methods with various inputs, print the results, and display execution times.

Java Implementation

public class ReverseString {
    // Reverses string using String concatenation
    public String reverseWithString(String input) {
        if (input == null) {
            return null;
        }
        String result = "";
        for (int i = input.length() - 1; i >= 0; i--) {
            result += input.charAt(i);
        }
        return result;
    }

    // Reverses string using StringBuilder
    public String reverseWithStringBuilder(String input) {
        if (input == null) {
            return null;
        }
        return new StringBuilder(input).reverse().toString();
    }

    // Main method to test both reverse methods and compare performance
    public static void main(String[] args) {
        ReverseString reverser = new ReverseString();

        // Test cases
        String[] testStrings = {
            "hello",           // Small string
            "",               // Empty string
            "a",              // Single character
            generateLargeString(100000) // Large string
        };

        for (int i = 0; i < testStrings.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Original string: \"" + (testStrings[i].length() > 20 ? testStrings[i].substring(0, 20) + "..." : testStrings[i]) + "\"");
            
            // Test String method
            long startTime = System.nanoTime();
            String resultString = reverser.reverseWithString(testStrings[i]);
            long stringTime = System.nanoTime() - startTime;
            System.out.println("String method result: \"" + (resultString != null && resultString.length() > 20 ? resultString.substring(0, 20) + "..." : resultString) + "\"");
            System.out.println("String method time: " + stringTime + " ns");

            // Test StringBuilder method
            startTime = System.nanoTime();
            String resultBuilder = reverser.reverseWithStringBuilder(testStrings[i]);
            long builderTime = System.nanoTime() - startTime;
            System.out.println("StringBuilder method result: \"" + (resultBuilder != null && resultBuilder.length() > 20 ? resultBuilder.substring(0, 20) + "..." : resultBuilder) + "\"");
            System.out.println("StringBuilder method time: " + builderTime + " ns\n");
        }
    }

    // Helper method to generate a large string
    private static String generateLargeString(int length) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append((char) ('a' + (i % 26)));
        }
        return sb.toString();
    }
}

Output

Running the main method produces (actual times may vary depending on the system):

Test case 1:
Original string: "hello"
String method result: "olleh"
String method time: 123456 ns
StringBuilder method result: "olleh"
StringBuilder method time: 7890 ns

Test case 2:
Original string: ""
String method result: ""
String method time: 4567 ns
StringBuilder method result: ""
StringBuilder method time: 3456 ns

Test case 3:
Original string: "a"
String method result: "a"
String method time: 5678 ns
StringBuilder method result: "a"
StringBuilder method time: 4321 ns

Test case 4:
Original string: "abcdefghijklmnopqrst..."
String method result: "zyxwvutsrqponmlkjihg..."
String method time: 1234567890 ns
StringBuilder method result: "zyxwvutsrqponmlkjihg..."
StringBuilder method time: 987654 ns

Explanation:

  • Test case 1: Reverses "hello" to "olleh"; StringBuilder is faster.
  • Test case 2: Empty string "" remains ""; both methods are fast.
  • Test case 3: Single character "a" remains "a"; similar performance.
  • Test case 4: Large string (100,000 characters); StringBuilder is significantly faster due to avoiding repeated string object creation.

How It Works

  • String Method:
    • Iterates from the last character to the first, building a new string via concatenation.
    • Each concatenation creates a new String object, leading to O(n^2) time for large strings.
  • StringBuilder Method:
    • Uses StringBuilder’s reverse method, which manipulates the internal character array in-place.
    • Highly efficient, O(n) time, as it avoids creating intermediate objects.
  • Performance Comparison:
    • Measures time using System.nanoTime() for both methods.
    • String concatenation is slow for large strings due to quadratic overhead.
    • StringBuilder is optimized for mutable string operations, showing significant speedup.
  • Main Method: Tests with small, empty, single-character, and large strings, printing results and execution times.
  • Trace (Test case 1):
    • String: "hello" → result = "" + 'o' + 'l' + 'l' + 'e' + 'h' = "olleh".
    • StringBuilder: Initializes with "hello", reverses to "olleh".

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
String MethodO(n^2)O(n)
StringBuilder MethodO(n)O(n)
Full AlgorithmO(n^2)O(n)

Note:

  • n is the length of the input string.
  • String method: O(n^2) time due to string concatenation creating new objects each iteration; O(n) space for the result.
  • StringBuilder method: O(n) time for in-place reversal; O(n) space for the StringBuilder.
  • Worst case: String method dominates with O(n^2) for large strings.

✅ Tip: Use StringBuilder for reversing large strings due to its linear time complexity. Test with large inputs to observe performance differences clearly.

⚠ Warning: Avoid String concatenation for large strings, as it creates multiple intermediate objects, leading to poor performance. Always check for null inputs to prevent NullPointerException.