From the free course Java Programming and Algorithmic Thinking Fundamentals on Lykke

String Manipulation

Key concepts: String Methods (charAt, indexOf) · Value Equality (.equals()) · Reference Equality (==) · String Initialization · Palindrome Detection

In-depth look at the String class, text processing, and the difference between value and reference equality.

String Manipulation

In the hierarchy of data representation, the String occupies a unique position in the Java ecosystem. While primitive types like int and double represent atomic numerical values, a String is a sophisticated object—a sequence of characters that serves as the primary medium for human-computer interaction. To the novice, a String is merely "text"; to the senior engineer, it is an immutable, heap-allocated object governed by specific memory-management rules and a rich API.

Understanding string manipulation is not merely about learning methods like substring() or indexOf(). It requires a deep comprehension of how Java handles object references, the distinction between value and identity, and the algorithmic efficiency of text processing. This article provides a rigorous exploration of the String class, from its underlying memory architecture to the implementation of classical algorithms like palindrome detection.

The Anatomy of a String: Initialization and Memory

What it is

In Java, a String is a non-primitive data type that represents a sequence of Unicode characters. Unlike a simple array of characters (char[]), the String class encapsulates the data and provides a suite of methods to interact with it. Crucially, Strings are immutable: once a String object is created, its internal character sequence cannot be altered.

Why it matters

Immutability provides several critical advantages:

  1. Security: Sensitive data (like passwords or file paths) cannot be changed by a called method.
  2. Thread Safety: Multiple threads can share a String instance without fear of corruption.
  3. Caching: Because Strings are constant, the Java Virtual Machine (JVM) can optimize memory through a process called interning.

How it works: The String Pool

When you initialize a String using a literal (e.g., String s = "Java"), the JVM checks the String Constant Pool—a special memory region within the Heap. If the literal already exists, the new variable simply points to the existing object. If you use the new keyword, you bypass this optimization, forcing the creation of a new object in the general Heap.

Initialization Method Syntax Memory Location Interning Behavior
Literal String s = "Hello"; String Constant Pool Reuses existing instances
Constructor String s = new String("Hello"); General Heap Always creates a new object
Concatenation String s = "A" + "B"; String Constant Pool Handled at compile-time for constants

Common Pitfalls: The "New" Trap

A common mistake among junior developers is using new String("text"). This is almost always redundant and inefficient, as it creates two objects (the literal in the pool and the object on the heap) where one would suffice.


Core String API: Navigation and Search

What it is

The String class provides methods to probe the contents of the character sequence without modifying the original object. The most fundamental of these are length(), charAt(), and indexOf().

Mechanics of Indexing

Java uses 0-based indexing. For a string of length $N$, the valid indices are the set of integers $I = {0, 1, \dots, N-1}$. Accessing an index $i \notin I$ results in a StringIndexOutOfBoundsException.

Essential Methods Table

Method Return Type Complexity Description
length() int $O(1)$ Returns the number of 16-bit Unicode characters.
charAt(int i) char $O(1)$ Returns the character at the specified index.
indexOf(String s) int $O(N \cdot M)$ Returns the index of the first occurrence of substring s, or -1 if not found.
substring(int b, int e) String $O(N)$ Returns a new string from index b (inclusive) to e (exclusive).
toLowerCase() String $O(N)$ Returns a new string with all characters converted to lowercase.

Concrete Example: Parsing a Domain

Consider the task of extracting the domain name from an email address. We can combine indexOf and substring to achieve this dynamically.

public class EmailParser {
    public static void main(String[] args) {
        String email = "professor.falken@wargames.edu";
        
        // Find the position of the '@' symbol
        int atSymbolIndex = email.indexOf("@");
        
        if (atSymbolIndex != -1) {
            // Extract everything after the '@'
            String domain = email.substring(atSymbolIndex + 1);
            System.out.println("Domain: " + domain);
        } else {
            System.out.println("Invalid email format.");
        }
    }
}

The Equality Paradox: == vs. .equals()

What it is

In Java, there is a vital distinction between Reference Equality and Value Equality.

  • Reference Equality (==): Checks if two variables point to the exact same memory address.
  • Value Equality (.equals()): Checks if two objects represent the same sequence of characters.

Why it matters

Because of the String Pool, two literals might share a reference, making == appear to work correctly. However, as soon as strings are generated dynamically (e.g., via StdIn or substring), they reside at different memory addresses. Using == on these strings will return false, even if their text is identical. This is perhaps the single most frequent source of logic errors in Java programming.

Derivation of Logic

Let $S_1$ and $S_2$ be String references.

  • $S_1 == S_2 \implies \text{Address}(S_1) = \text{Address}(S_2)$
  • $S_1.equals(S_2) \implies \forall i \in [0, \text{length}), S_1[i] = S_2[i]$

The Golden Rule of Strings: Never use == to compare the content of two strings. Always use the .equals() method.

Comparison Table: Equality Operators

Feature == Operator .equals() Method
Type of Check Identity (Reference) Content (State)
Compares Memory Addresses Character Sequences
Use Case Checking if two references are the same object Comparing user input, file data, or logic
Null Safety Safe (returns false if one is null) Throws NullPointerException if called on a null object

Concrete Example: The Reference Trap

public class EqualityDemo {
    public static void main(String[] args) {
        String s1 = "hello";
        String s2 = "hello";
        String s3 = new String("hello");

        // s1 and s2 point to the same literal in the String Pool
        System.out.println(s1 == s2);      // true
        
        // s3 is a new object on the heap, despite having the same value
        System.out.println(s1 == s3);      // false
        
        // Value equality is consistent
        System.out.println(s1.equals(s3)); // true
    }
}

Algorithmic Application: Palindrome Detection

What it is

A palindrome is a string that reads the same forward and backward (e.g., "racecar", "madam", "12321"). Detecting a palindrome is a classic exercise in string traversal and conditional logic.

How it works: The Two-Pointer Approach

The most efficient way to check for a palindrome is to compare characters from both ends of the string, moving toward the center. If any pair of characters fails to match, the string is not a palindrome.

Algorithm Steps:

  1. Initialize left pointer to 0.
  2. Initialize right pointer to length() - 1.
  3. While left < right:
    • Compare charAt(left) and charAt(right).
    • If not equal, return false.
    • Increment left, decrement right.
  4. If the loop completes, return true.

Complexity Analysis

  • Time Complexity: $O(N)$, where $N$ is the length of the string. We visit each character at most once.
  • Space Complexity: $O(1)$, as we only store two integer pointers regardless of the string size.

Implementation in Java

public class PalindromeChecker {
    public static boolean isPalindrome(String s) {
        if (s == null) return false;
        
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false; // Mismatch found
            }
            left++;
            right--;
        }
        return true; // Symmetric throughout
    }

    public static void main(String[] args) {
        String test = "racecar";
        if (isPalindrome(test)) {
            System.out.println(test + " is a palindrome.");
        }
    }
}

Variations: Case Sensitivity and Recursion

In many real-world applications, palindromes are considered case-insensitive ("Madam" should be a palindrome). This is handled by calling s.toLowerCase() before processing. Alternatively, the problem can be solved recursively:

  • Base Case: If length <= 1, return true.
  • Recursive Step: If charAt(0) == charAt(length-1), return isPalindrome(substring(1, length-1)).

Advanced Manipulation: Immutability and the StringBuilder

The Problem with Concatenation

Because Strings are immutable, every time you perform a concatenation (s = s + "!"), Java does not modify the existing string. Instead, it:

  1. Creates a new StringBuilder (or similar buffer).
  2. Copies the old string.
  3. Appends the new characters.
  4. Converts the result back to a new String object.

In a loop running $N$ times, this results in $O(N^2)$ time complexity because of the repeated copying of increasingly large strings.

The Solution: StringBuilder

For intensive string construction (like building a large report or reversing a long string), use the StringBuilder class. It maintains a mutable array of characters, allowing for $O(1)$ appends.

Feature String StringBuilder
Mutability Immutable Mutable
Performance Slow for frequent modifications High performance for modifications
Memory Creates new objects for each change Modifies the same internal buffer
Thread Safety Naturally Thread-Safe Not Thread-Safe

Worked Example: String Reversal

public class Reversal {
    public static String reverse(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

Common Pitfalls and Best Practices

1. The null vs. Empty String Distinction

A null string means the reference points to nothing. An empty string ("") is a valid String object with a length of 0. Calling .length() on a null reference will crash your program.

2. Off-by-One Errors in substring()

The substring(start, end) method is inclusive of the start index but exclusive of the end index. This design allows the length of the resulting substring to be calculated simply as end - start.

3. Ignoring Return Values

Since Strings are immutable, methods like toUpperCase() do not change the string you call them on. They return a new string.

  • Incorrect: s.toUpperCase();
  • Correct: s = s.toUpperCase();

4. Parsing Command-Line Arguments

Strings are the default format for command-line input. To use them as numbers, you must use wrapper class methods:

int count = Integer.parseInt(args[0]);
double price = Double.parseDouble(args[1]);

Summary of String Manipulation Complexity

To conclude, the following table summarizes the computational costs of the operations discussed. As a developer, choosing the right operation for the scale of your data is the hallmark of professional engineering.

Operation Method Complexity Notes
Access charAt() $O(1)$ Direct array indexing internally.
Search indexOf() $O(N \cdot M)$ Can be optimized by JVM (Boyer-Moore).
Comparison .equals() $O(N)$ Must check every character in worst case.
Concatenation + operator $O(N)$ Linear time due to new object creation.
Building StringBuilder.append() $O(1)$ Amortized constant time.
Extraction substring() $O(N)$ Copies the character range.
String Manipulation - Java Programming and Algorithmic Thinking Fundamentals - diagram 1
String Manipulation - Java Programming and Algorithmic Thinking Fundamentals - diagram 1
String Manipulation - Java Programming and Algorithmic Thinking Fundamentals - diagram 2
String Manipulation - Java Programming and Algorithmic Thinking Fundamentals - diagram 2

Source Materials

Study Java Programming and Algorithmic Thinking Fundamentals on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Java Programming and Algorithmic Thinking Fundamentals · Browse more course pages

String Manipulation — Java Programming and Algorithmic Thinking Fundamentals | Lykke