Java Data Structures and Algorithms for Beginners

String Data Structure

Definition and Concepts

A string is a sequence of characters used to represent text in programming. In Java, the String class is a fundamental data structure that is immutable, meaning its content cannot be changed after creation. Strings are stored as arrays of characters internally, but Java’s String class provides a high-level interface for manipulating text. You can visualize a string as a chain of characters, such as "Hello", where each character occupies a specific position (index) starting from 0. Strings support operations like concatenation, substring extraction, and searching, making them essential for text processing. Java also provides mutable alternatives like StringBuilder and StringBuffer for scenarios requiring frequent modifications.

Why Use It?

Strings are used to handle and manipulate textual data in a wide range of applications, from user input processing to file parsing. Their immutability in Java ensures thread safety and consistency, making them ideal for constant or shared text data. Strings provide a rich set of methods for searching, modifying, and comparing text, simplifying complex text operations. For performance-critical applications, mutable classes like StringBuilder are used to reduce overhead from creating multiple string objects.

Where to Use? (Real-Life Examples)

• Text Processing: Text editors use strings to store and manipulate document content, such as formatting or searching text.
• Web Development: Web applications use strings to process URLs, HTML content, and user input, such as form data.
• Data Parsing: CSV or JSON parsers use strings to extract fields and values from structured data files.
• Search and Validation: Search engines and form validators use strings to match patterns (e.g., email validation) or search for keywords.

Explain Operations

• Concatenation: This operation combines two strings into a new string. It has a time complexity of O(n), where n is the total length of the resulting string.
• Substring Extraction: This operation extracts a portion of the string based on start and end indices. It has a time complexity of O(n) in Java due to string immutability.
• Search (Index Of): This operation finds the index of a substring or character within the string. It has a time complexity of O(n*m) in the worst case, where n is the string length and m is the substring length.
• Length: This operation returns the number of characters in the string. It has a time complexity of O(1).
• Character Access: This operation retrieves the character at a specific index. It has a time complexity of O(1).

Java Implementation

The following Java code demonstrates common string operations using the String class and introduces StringBuilder for mutable string manipulation.

public class StringExamples {
    // Concatenation: Combines two strings
    public String concatenate(String str1, String str2) {
        return str1 + str2; // Uses + operator for concatenation
    }

    // Substring: Extracts a portion of the string
    public String getSubstring(String str, int start, int end) {
        if (start < 0 || end > str.length() || start > end) {
            throw new IllegalArgumentException("Invalid start or end index.");
        }
        return str.substring(start, end); // Returns substring from start to end-1
    }

    // Search: Finds the index of a substring
    public int findIndex(String str, String target) {
        return str.indexOf(target); // Returns index of first occurrence or -1 if not found
    }

    // Length: Returns the number of characters
    public int getLength(String str) {
        return str.length(); // Returns the string length
    }

    // Character Access: Gets character at index
    public char getCharAt(String str, int index) {
        if (index < 0 || index >= str.length()) {
            throw new IllegalArgumentException("Invalid index.");
        }
        return str.charAt(index); // Returns character at specified index
    }

    // StringBuilder Example: Demonstrates mutable string manipulation
    public String buildString(String[] parts) {
        StringBuilder builder = new StringBuilder();
        for (String part : parts) {
            builder.append(part); // Appends each part to the builder
        }
        return builder.toString(); // Converts StringBuilder to String
    }
}

How It Works

1. Concatenation:
   • The concatenate method uses the + operator, which internally creates a new String object combining str1 and str2.
   • For example, concatenate("Hello", " World") creates a new string "Hello World".
2. Substring Extraction:
   • The getSubstring method calls str.substring(start, end), which creates a new string containing characters from index start to end-1.
   • For example, getSubstring("Hello", 1, 4) returns "ell".
3. Search (Index Of):
   • The findIndex method uses str.indexOf(target) to return the starting index of target in str or -1 if not found.
   • For example, findIndex("Hello", "ll") returns 2.
4. Length:
   • The getLength method calls str.length() to return the number of characters.
   • For example, getLength("Hello") returns 5.
5. Character Access:
   • The getCharAt method uses str.charAt(index) to return the character at the specified index.
   • For example, getCharAt("Hello", 1) returns 'e'.
6. StringBuilder Example:
   • The buildString method uses StringBuilder to efficiently append multiple strings from an array, then converts the result to a String.
   • For example, buildString(new String[]{"He", "llo"}) returns "Hello".

Complexity Analysis Table

Note:

• n is the length of the string (or total length for concatenation).
• m is the length of the substring in indexOf.
• StringBuilder append is O(1) amortized due to dynamic resizing.

Key Differences / Notes

• String Immutability:
  • Java’s String class is immutable, so operations like concatenation and substring create new strings, increasing space complexity.
  • StringBuilder and StringBuffer are mutable, reducing overhead for frequent modifications.
• String vs. StringBuilder/StringBuffer:
  • Use String for constant or infrequently modified text due to its immutability and thread safety.
  • Use StringBuilder for single-threaded, mutable string operations, or StringBuffer for thread-safe mutable operations.
• Thread Safety:
  • String and StringBuilder are not thread-safe for modifications (though String is immutable). StringBuffer is thread-safe but slower.
• String Pool:
  • Java maintains a string pool, a special area in the heap (part of the constant pool in the PermGen or Metaspace, depending on the Java version), to store unique string literals and interned strings. When a string literal (e.g., "Hello") is created, Java checks the string pool. If the string exists, the reference is reused; otherwise, a new string is added to the pool. This optimizes memory usage for repeated literals.
  • The intern() method can manually add a string to the pool, ensuring that identical strings share the same reference. For example, new String("Hello").intern() returns the pooled reference if "Hello" exists.
  • String pool usage reduces memory overhead but requires careful handling in performance-critical applications, as excessive interning can increase pool size and lookup time.

✅ Tip: Use StringBuilder for concatenating strings in a loop to avoid the overhead of creating multiple String objects. For simple, one-time concatenations, the + operator is sufficient and readable. Use String.intern() to leverage the string pool for memory optimization when dealing with frequently reused strings.

⚠ Warning: Avoid excessive string concatenation in loops using the + operator, as it creates multiple intermediate String objects, leading to O(n²) time complexity. Use StringBuilder for better performance. Be cautious with String.intern(), as overusing it can bloat the string pool and degrade performance.

Exercises

1. Reverse a String: Write a Java program that reverses a string using both String methods and StringBuilder. Compare their performance for large strings.
2. Palindrome Checker: Implement a method to check if a string is a palindrome (ignoring case and non-alphanumeric characters). Test with various inputs.
3. String Compression: Create a program that compresses a string by replacing repeated characters with their count (e.g., "aabbb" becomes "a2b3"). Use StringBuilder for efficiency.
4. Substring Frequency: Write a method to count the occurrences of a substring in a string using indexOf. Test with overlapping and non-overlapping cases.
5. String Pool Experiment: Write a Java program that demonstrates the string pool by comparing string literals, new String() objects, and interned strings using == and equals(). Analyze memory usage and equality behavior.