String immutability in Java - Time & Space Complexity

Time Complexity: String immutability

O(n^2)

Understanding Time Complexity

We want to understand how working with strings in Java affects the time it takes to run code.

Specifically, how does changing strings impact performance as the string size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

String s = "";
for (int i = 0; i < n; i++) {
    s = s + "a";
}
    

This code builds a string by adding one character at a time inside a loop.

Identify Repeating Operations

• Primary operation: Adding a character to the string inside the loop.
• How many times: The loop runs n times, repeating the addition each time.

How Execution Grows With Input

Each time we add a character, Java creates a new string by copying the old one and adding the new character.

Input Size (n)	Approx. Operations
10	About 55 copies (1+2+...+10)
100	About 5,050 copies
1000	About 500,500 copies

Pattern observation: The work grows much faster than the input size; it grows roughly like the square of n.

Final Time Complexity

Time Complexity: O(n2)

This means the time to build the string grows very quickly as the string gets longer, because each addition copies the whole string again.

Common Mistake

[X] Wrong: "Adding characters to a string in a loop takes time proportional to the number of characters only."

[OK] Correct: Because strings are immutable, each addition copies the entire string so far, making the total work much larger than just n.

Interview Connect

Understanding how string immutability affects performance helps you write better code and explain your choices clearly in interviews.

Self-Check

What if we used a StringBuilder instead of adding strings directly? How would the time complexity change?

Practice

1. What does it mean that a String in Java is immutable?

easy

A. Once created, the string cannot be changed.

B. The string can be changed anytime.

C. The string changes automatically when printed.

D. The string can only be changed inside loops.

Solution

1. Step 1: Understand the meaning of immutability

   Immutability means the object cannot be changed after creation.

2. Step 2: Apply this to Java Strings

   Java strings cannot be modified once created; any change creates a new string.

3. Final Answer:

   Once created, the string cannot be changed. -> Option A

4. Quick Check:

   String immutability = cannot change after creation [OK]

Hint: Immutable means no change allowed after creation [OK]

Common Mistakes:

• Thinking strings can be changed directly
• Confusing immutability with constant variables
• Assuming strings change when printed

2. Which of the following is the correct way to create a new string by changing a character in an existing string str?

easy

A. str.charAt(0) = 'A';

B. str[0] = 'A';

C. str = "A" + str.substring(1);

D. str.replaceChar(0, 'A');

Solution

1. Step 1: Check syntax for changing characters in strings

   Strings are immutable, so direct assignment like str.charAt(0) = 'A' is invalid.

2. Step 2: Use substring to create a new string

   Concatenate "A" with the substring from index 1 to form a new string.

3. Final Answer:

   str = "A" + str.substring(1); -> Option C

4. Quick Check:

   Use substring + concat to change string [OK]

Hint: Use substring and concat to create new string [OK]

Common Mistakes:

• Trying to assign directly to string characters
• Using array-like indexing on strings
• Using non-existent methods like replaceChar

3. What is the output of the following code?

String s = "hello";
s.toUpperCase();
System.out.println(s);

medium

A. HELLO

B. hello

C. null

D. HELLOhello

Solution

1. Step 1: Understand that strings are immutable

   The method toUpperCase() returns a new string but does not change the original string s.

2. Step 2: Check what is printed

   Since s was not reassigned, printing s outputs the original string "hello".

3. Final Answer:

   hello -> Option B

4. Quick Check:

   Original string unchanged = hello [OK]

Hint: toUpperCase returns new string; original stays same [OK]

Common Mistakes:

• Assuming toUpperCase changes original string
• Expecting uppercase output without reassignment
• Confusing method effect with print output

4. Find the error in this code snippet:

String s = "test";
s.charAt(0) = 'T';
System.out.println(s);

medium

A. Cannot assign to charAt() result; strings are immutable.

B. Missing semicolon after declaration.

C. charAt() method does not exist for String.

D. System.out.println() cannot print strings.

Solution

1. Step 1: Check usage of charAt()

   The method charAt() returns a character but cannot be assigned a new value.

2. Step 2: Understand string immutability

   Strings cannot be changed by assigning to characters; this causes a compile error.

3. Final Answer:

   Cannot assign to charAt() result; strings are immutable. -> Option A

4. Quick Check:

   charAt() result is read-only [OK]

Hint: charAt() returns char, cannot assign to it [OK]

Common Mistakes:

• Trying to assign to charAt()
• Thinking strings are mutable
• Ignoring compile errors on assignment

5. You want to replace all occurrences of the letter 'a' with 'b' in a string input. Which code correctly does this considering string immutability?

hard

A. input.replace('a', 'b'); System.out.println(input);

B. input.charAt(0) = 'b'; System.out.println(input);

C. input.toCharArray()[0] = 'b'; System.out.println(input);

D. input = input.replace('a', 'b'); System.out.println(input);

Solution

1. Step 1: Understand replace() returns new string

   The replace() method returns a new string with replacements but does not change the original.

2. Step 2: Assign the new string back to input

   To update input, assign the result of replace() back to it before printing.

3. Final Answer:

   input = input.replace('a', 'b'); System.out.println(input); -> Option D

4. Quick Check:

   Assign replace result to variable to update string [OK]

Hint: Assign replace() result to variable to update string [OK]

Common Mistakes:

• Calling replace() without assignment
• Trying to assign to charAt() or array elements
• Expecting original string to change automatically