String Basics and Memory Representation in DSA Java - Time & Space Complexity

Time Complexity: String Basics and Memory Representation

O(n)

Understanding Time Complexity

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

How does the length of a string affect the time to do basic operations like copying or comparing?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class StringExample {
    public static void main(String[] args) {
        String s1 = "hello";
        String s2 = new String(s1);
        boolean isEqual = s1.equals(s2);
    }
}
    

This code creates a new string by copying an existing one and then compares the two strings for equality.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying characters from one string to another and comparing characters one by one.
• How many times: Once for each character in the string during copy and once during comparison.

How Execution Grows With Input

As the string length grows, the number of characters copied and compared grows the same way.

Input Size (n)	Approx. Operations
10	About 10 character copies and 10 comparisons
100	About 100 character copies and 100 comparisons
1000	About 1000 character copies and 1000 comparisons

Pattern observation: The work grows directly with the string length; doubling the string doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to copy or compare strings grows linearly with the string length.

Common Mistake

[X] Wrong: "Comparing two strings is always a constant time operation because they are objects."

[OK] Correct: Actually, comparing strings checks each character until a difference is found or the end is reached, so it depends on string length.

Interview Connect

Understanding how string operations scale helps you write efficient code and answer questions about performance in real projects.

Self-Check

"What if we used string references directly without copying? How would the time complexity change for comparison?"

Practice

1. What is the correct way to create a string literal in Java?

easy

A. String s = 'Hello';

B. String s = new String();

C. String s = "Hello";

D. String s = String();

Solution

1. Step 1: Understand string literal syntax

   In Java, string literals are enclosed in double quotes, so "Hello" is correct.

2. Step 2: Check each option

   String s = "Hello"; uses double quotes correctly. String s = new String(); creates an empty string object but not a literal. String s = 'Hello'; uses single quotes which are for characters, not strings. String s = String(); is invalid syntax.

3. Final Answer:

   String s = "Hello"; -> Option C

4. Quick Check:

   String literal uses double quotes = A [OK]

Hint: Use double quotes for string literals in Java [OK]

Common Mistakes:

• Using single quotes for strings
• Trying to call String() like a function
• Confusing new String() with literal

2. Which of the following is the correct syntax to compare two strings s1 and s2 for content equality in Java?

easy

A. if (s1.equals(s2))

B. if (s1 == s2)

C. if (s1 = s2)

D. if (s1.compare(s2))

Solution

1. Step 1: Understand string comparison in Java

   Using == compares references (memory addresses), not content. To compare content, use the equals() method.

2. Step 2: Evaluate each option

   if (s1 == s2) compares references, not content. if (s1.equals(s2)) correctly uses equals() method. if (s1 = s2) uses assignment (=) which is invalid in condition. if (s1.compare(s2)) uses a non-existent method compare().

3. Final Answer:

   if (s1.equals(s2)) -> Option A

4. Quick Check:

   Use equals() for string content comparison = B [OK]

Hint: Use equals() method to compare string contents [OK]

Common Mistakes:

• Using == to compare strings
• Using assignment operator in if condition
• Calling non-existent methods

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

String s1 = "hello";
String s2 = "hello";
String s3 = new String("hello");
System.out.println(s1 == s2);
System.out.println(s1 == s3);
System.out.println(s1.equals(s3));

medium

A. true
false
true

B. false
false
true

C. true
true
true

D. false
true
false

Solution

1. Step 1: Understand string pool and new String()

   s1 and s2 are string literals and point to the same object in the string pool, so s1 == s2 is true. s3 is a new String object, so s1 == s3 is false because they reference different objects.

2. Step 2: Check equals() method

   s1.equals(s3) compares content and both have "hello", so it returns true.

3. Final Answer:

   true false true -> Option A

4. Quick Check:

   == compares references, equals() compares content = C [OK]

Hint: == checks memory, equals() checks string content [OK]

Common Mistakes:

• Assuming new String() shares reference
• Confusing == with equals()
• Ignoring string pool behavior

4. Identify the error in the following code snippet:

String s = "test";
if (s == "test") {
    System.out.println("Match");
} else {
    System.out.println("No Match");
}

medium

A. System.out.println syntax is incorrect

B. Missing semicolon after string declaration

C. String literals cannot be compared

D. Using == to compare strings can cause unexpected results

Solution

1. Step 1: Check string comparison method

   The code uses == to compare strings, which compares references, not content. This can cause unexpected results if strings are not from the pool.

2. Step 2: Verify other syntax

   There is no missing semicolon, string literals can be compared with equals(), and System.out.println syntax is correct.

3. Final Answer:

   Using == to compare strings can cause unexpected results -> Option D

4. Quick Check:

   Use equals() for string comparison, not == = A [OK]

Hint: Avoid == for strings; use equals() instead [OK]

Common Mistakes:

• Thinking == compares string content
• Ignoring string pool behavior
• Assuming syntax errors where none exist

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

String a = "Java";
String b = "Ja" + "va";
String c = new String("Java");
System.out.println(a == b);
System.out.println(a == c);
System.out.println(a.equals(c));

Explain why the outputs are as they are.

hard

A. false
true
false

B. true
false
true

C. true
true
true

D. false
false
true

Solution

1. Step 1: Analyze string concatenation with literals

   Strings "Ja" and "va" are literals concatenated at compile time, so b points to the same string pool object as a. Therefore, a == b is true.

2. Step 2: Understand new String() behavior

   c is a new String object created at runtime, so a == c is false because they reference different objects. However, a.equals(c) compares content and returns true.

3. Final Answer:

   true false true -> Option B

4. Quick Check:

   Compile-time concat shares pool, new String() creates new object = D [OK]

Hint: Compile-time concat shares pool; new String() creates new object [OK]

Common Mistakes:

• Assuming runtime concat shares pool
• Confusing == with equals()
• Ignoring compile-time optimization