Why strings are special in Java - Performance Analysis

Time Complexity: Why strings are special in Java

O(n²)

Understanding Time Complexity

Strings in Java are handled differently than other objects. This affects how fast operations on strings run.

We want to understand how the time to work with strings grows as the string gets longer.

Scenario Under Consideration

Analyze the time complexity of concatenating strings using the + operator.

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

This code builds a string by adding numbers one by one in a loop.

Identify Repeating Operations

Look at what repeats as the input grows.

• Primary operation: String concatenation inside the loop.
• How many times: The loop runs n times, and each concatenation copies the whole string built so far.

How Execution Grows With Input

Each time we add to the string, Java copies the entire current string to make a new one.

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 step copies all before it.

Common Mistake

[X] Wrong: "Concatenating strings in a loop is always fast and runs in linear time."

[OK] Correct: Each concatenation creates a new string by copying the old one, so the total work adds up much more than just n steps.

Interview Connect

Understanding how strings work helps you write faster code and shows you know how Java handles objects behind the scenes.

Self-Check

"What if we used a StringBuilder instead of + for concatenation? How would the time complexity change?"

Practice

1. Why are strings considered special objects in Java compared to other objects?

easy

A. Because Java stores string literals in a special pool to save memory

B. Because strings can only store numbers

C. Because strings are primitive data types

D. Because strings cannot be compared using methods

Solution

1. Step 1: Understand string storage in Java

   Java stores string literals in a special memory area called the string pool to reuse them and save memory.

2. Step 2: Compare with other objects

   Other objects do not have this special pool and are stored separately each time they are created.

3. Final Answer:

   Because Java stores string literals in a special pool to save memory -> Option A

4. Quick Check:

   String pool = special memory reuse [OK]

Hint: Remember: string literals share memory in a pool [OK]

Common Mistakes:

• Thinking strings are primitive types
• Believing strings only store numbers
• Assuming strings cannot be compared

2. Which of the following is the correct way to create a string literal in Java?

easy

A. String s = new String('hello');

B. String s = "hello";

C. String s = 'hello';

D. String s = hello;

Solution

1. Step 1: Identify correct string literal syntax

   In Java, string literals must be enclosed in double quotes, like "hello".

2. Step 2: Check other options for errors

   String s = new String('hello'); uses single quotes which are for chars, String s = 'hello'; uses single quotes incorrectly, String s = hello; lacks quotes entirely.

3. Final Answer:

   String s = "hello"; -> Option B

4. Quick Check:

   Strings use double quotes "" [OK]

Hint: Use double quotes for strings, single for chars [OK]

Common Mistakes:

• Using single quotes for strings
• Omitting quotes around text
• Confusing char and string syntax

3. What will be the output of the following Java code?

String a = "hello";
String b = "hello";
System.out.println(a == b);

medium

A. false

B. Runtime exception

C. Compilation error

D. true

Solution

1. Step 1: Understand string literal pooling

   Both variables a and b refer to the same string literal "hello" in the string pool, so they point to the same object.

2. Step 2: Evaluate '==' operator on strings

   The '==' operator compares references, and since both refer to the same object, it returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Same literal references = true [OK]

Hint: == true if both strings share the same pool object [OK]

Common Mistakes:

• Assuming '==' compares string content
• Expecting false because of separate variables
• Confusing '==' with equals() method

4. Identify the error in the following code snippet:

String s1 = new String("test");
String s2 = new String("test");
if (s1 == s2) {
    System.out.println("Equal");
} else {
    System.out.println("Not Equal");
}

medium

A. Using '==' to compare string contents instead of equals()

B. Missing semicolon after string declarations

C. Incorrect string initialization syntax

D. Cannot create strings with new keyword

Solution

1. Step 1: Understand '==' vs equals() for strings

   '==' compares references, not content. Since s1 and s2 are different objects, '==' returns false.

2. Step 2: Correct way to compare string content

   Use s1.equals(s2) to compare the actual text inside the strings.

3. Final Answer:

   Using '==' to compare string contents instead of equals() -> Option A

4. Quick Check:

   Use equals() for string content comparison [OK]

Hint: Use equals() to compare string text, not '==' [OK]

Common Mistakes:

• Using '==' to compare string values
• Thinking new String() creates same object
• Ignoring string pool behavior

5. Given the code below, what will be the output?

String s1 = "Java";
String s2 = new String("Java");
String s3 = s2.intern();
System.out.println(s1 == s2);
System.out.println(s1 == s3);

Why does this happen?

hard

A. false false - all are different objects

B. true false - new String creates pooled string

C. false true - intern() returns the pooled string reference

D. true true - all strings are pooled automatically

Solution

1. Step 1: Analyze s1 and s2 references

   s1 is a string literal in the pool, s2 is a new String object outside the pool, so s1 == s2 is false.

2. Step 2: Understand intern() method effect

   s3 = s2.intern() returns the reference from the string pool for "Java", which is the same as s1, so s1 == s3 is true.

3. Final Answer:

   false true - intern() returns the pooled string reference -> Option C

4. Quick Check:

   intern() returns pool reference [OK]

Hint: intern() returns pooled string reference [OK]

Common Mistakes:

• Assuming new String() returns pooled string
• Thinking '==' compares string content
• Ignoring intern() method purpose