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

String Reversal

Problem Statement

Write a Java program that implements two methods to reverse a string: one using StringBuilder and another using StringBuffer. The program should return the reversed string and compare the performance of both methods for large inputs (e.g., a string of 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 on a conveyor belt, using two different tools: StringBuilder for a quick, single-user operation, and StringBuffer for a safer, multi-user operation, to see which gets the job done faster.

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 StringBuilder and StringBuffer methods. Constraints:

  • String length is between 0 and 10^6.
  • The string contains any printable ASCII characters.
  • The input 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 generally faster than StringBuffer due to lack of synchronization.

Pseudocode

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 reverseWithStringBuffer(input)
    IF input is null THEN
        RETURN null
    ENDIF
    CREATE stringBuffer with input
    CALL reverse on stringBuffer
    RETURN stringBuffer 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 reverseWithStringBuilder(string)
        SET builderTime to current time - startTime
        PRINT reversed string and builderTime
        SET startTime to current time
        CALL reverseWithStringBuffer(string)
        SET bufferTime to current time - startTime
        PRINT reversed string and bufferTime
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. 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.
  2. StringBuffer Method: a. Check if the input is null; if so, return null. b. Create a StringBuffer with the input string. c. Use StringBuffer’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 StringReversal {
    // Reverses string using StringBuilder
    public String reverseWithStringBuilder(String input) {
        if (input == null) {
            return null;
        }
        return new StringBuilder(input).reverse().toString();
    }

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

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

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

            // Test StringBuffer method
            startTime = System.nanoTime();
            String resultBuffer = reverser.reverseWithStringBuffer(testStrings[i]);
            long bufferTime = System.nanoTime() - startTime;
            System.out.println("StringBuffer result: \"" + (resultBuffer != null && resultBuffer.length() > 20 ? resultBuffer.substring(0, 20) + "..." : resultBuffer) + "\"");
            System.out.println("StringBuffer time: " + bufferTime + " 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"
StringBuilder result: "olleh"
StringBuilder time: 7890 ns
StringBuffer result: "olleh"
StringBuffer time: 9123 ns

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

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

Test case 4:
Original string: "abcdefghijklmnopqrst..."
StringBuilder result: "zyxwvutsrqponmlkjihg..."
StringBuilder time: 987654 ns
StringBuffer result: "zyxwvutsrqponmlkjihg..."
StringBuffer time: 1234567 ns

Explanation:

  • Test case 1: Reverses "hello" to "olleh"; StringBuilder is slightly 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 faster than StringBuffer due to lack of synchronization overhead.

How It Works

  • StringBuilder Method:
    • Uses StringBuilder’s reverse method, which manipulates the internal character array in-place.
    • Non-thread-safe, optimized for single-threaded use, making it faster.
  • StringBuffer Method:
    • Uses StringBuffer’s reverse method, also manipulating the internal array.
    • Thread-safe due to synchronization, adding slight overhead, making it slower.
  • Performance Comparison:
    • Measures time using System.nanoTime() for both methods.
    • StringBuilder is faster, especially for large strings, as it avoids synchronization.
    • StringBuffer’s synchronization adds overhead, noticeable in large inputs.
  • Main Method: Tests with small, empty, single-character, and large strings, printing results and execution times.
  • Trace (Test case 1):
    • StringBuilder: Initializes with "hello", reverses to "olleh".
    • StringBuffer: Initializes with "hello", reverses to "olleh".
  • Key Difference: StringBuilder is faster for single-threaded applications; StringBuffer is safer for multi-threaded contexts.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
StringBuilder ReverseO(n)O(n)
StringBuffer ReverseO(n)O(n)
Full AlgorithmO(n)O(n)

Note:

  • n is the length of the input string.
  • Time complexity: O(n) for both StringBuilder and StringBuffer, as reverse swaps characters in-place.
  • Space complexity: O(n) for the internal character array in both classes.
  • StringBuilder is faster in practice due to no synchronization; StringBuffer has overhead.
  • Worst case: O(n) time and O(n) space for both.

✅ Tip: Use StringBuilder for single-threaded applications to reverse strings efficiently. Test with large inputs to observe performance differences between StringBuilder and StringBuffer.

⚠ Warning: Use StringBuffer only in multi-threaded environments where thread safety is required, as its synchronization overhead can slow down performance. Always check for null inputs to prevent NullPointerException.