How Strings Work Differently Across Languages in DSA Java - Complexity Walkthrough

Time Complexity: How Strings Work Differently Across Languages

O(n²)

Understanding Time Complexity

Strings are used everywhere in programming, but how they work can change the time it takes to do things with them.

We want to see how string operations grow in cost as the string gets longer in Java compared to other languages.

Scenario Under Consideration

Analyze the time complexity of the following Java code snippet that concatenates strings in a loop.

public class StringConcat {
    public static void main(String[] args) {
        String result = "";
        for (int i = 0; i < 5; i++) {
            result += i;
        }
        System.out.println(result);
    }
}
    

This code adds numbers to a string one by one using the + operator inside a loop.

Identify Repeating Operations

Look for repeated actions that cost time.

• Primary operation: String concatenation inside the loop.
• How many times: 5 times (once per loop iteration).
• Each concatenation creates a new string by copying old content plus new part.

How Execution Grows With Input

As the string grows, each new concatenation copies more characters, so the work grows faster than the number of loops.

Input Size (n)	Approx. Operations
5	~15 copies (1+2+3+4+5)
10	~55 copies (sum 1 to 10)
100	~5050 copies (sum 1 to 100)

Pattern observation: The total work grows roughly like the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if the string length doubles, the time to concatenate grows about four times.

Common Mistake

[X] Wrong: "String concatenation in a loop is always fast and linear time."

[OK] Correct: In Java, strings are immutable, so each concatenation copies all characters, making it slower as the string grows.

Interview Connect

Understanding how strings work helps you write efficient code and explain your choices clearly in interviews.

Self-Check

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

Practice

1. In Java, which of the following statements about String objects is true?

easy

A. Strings are stored as linked lists of characters.

B. Strings can be changed directly by modifying their characters.

C. Strings are immutable, meaning once created, they cannot be changed.

D. Strings are always stored in the stack memory.

Solution

1. Step 1: Understand Java String immutability

   In Java, String objects cannot be changed after creation. Any modification creates a new String object.

2. Step 2: Compare other options

   Strings are not linked lists, and they are stored in heap memory, not stack.

3. Final Answer:

   Strings are immutable, meaning once created, they cannot be changed. -> Option C

4. Quick Check:

   Java String immutability = true [OK]

Hint: Remember: Java Strings never change after creation [OK]

Common Mistakes:

• Thinking Strings can be changed in place
• Confusing String storage with primitive types
• Assuming Strings are linked lists

2. Which of the following is the correct way to create a new String object in Java?

easy

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

B. String s = String("hello");

C. String s = new string("hello");

D. String s = 'hello';

Solution

1. Step 1: Check Java String creation syntax

   The correct syntax uses the keyword new and capitalized String class: new String("hello").

2. Step 2: Identify incorrect options

   String s = String("hello"); misses new, C uses lowercase string, and D uses single quotes which are for chars, not Strings.

3. Final Answer:

   String s = new String("hello"); -> Option A

4. Quick Check:

   Correct String constructor syntax = String s = new String("hello"); [OK]

Hint: Use new String("text") with capital S and double quotes [OK]

Common Mistakes:

• Using single quotes for Strings
• Using lowercase 'string' instead of 'String'
• Omitting the new keyword

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

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

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Understand String literals and pooling in Java

   Both a and b refer to the same String literal in the String pool, so a == b compares the same object reference.

2. Step 2: Evaluate the == operator on String literals

   Since both point to the same object, a == b returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   String literal pooling makes == true [OK]

Hint: String literals share references, so == returns true [OK]

Common Mistakes:

• Confusing == with .equals() for content check
• Assuming == always returns false for Strings
• Ignoring String pool behavior

4. Identify the error in the following Java code snippet:

String s = "hello";
s[0] = 'H';
System.out.println(s);

medium

A. Strings are immutable; characters cannot be changed by index.

B. Syntax error: single quotes cannot be used for characters.

C. Runtime error: index out of bounds.

D. No error; output will be "Hello".

Solution

1. Step 1: Check String immutability in Java

   Strings cannot be changed by modifying characters at an index because they are immutable.

2. Step 2: Analyze the code error

   Attempting s[0] = 'H'; causes a compile-time error since Strings do not support indexing for assignment.

3. Final Answer:

   Strings are immutable; characters cannot be changed by index. -> Option A

4. Quick Check:

   Immutable Strings prevent index assignment [OK]

Hint: Strings can't change characters by index in Java [OK]

Common Mistakes:

• Trying to modify String characters directly
• Confusing char arrays with Strings
• Expecting runtime error instead of compile error

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

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

hard

A. true\nfalse

B. false\ntrue

C. false\nfalse

D. true\ntrue

Solution

1. Step 1: Understand new String() vs String literal

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

2. Step 2: Understand intern() method

   s3 is the interned version of s1, which returns the pooled String equal to "test", same as s2. So s2 == s3 is true.

3. Final Answer:

   false true -> Option B

4. Quick Check:

   new String != literal, intern() returns pooled String [OK]

Hint: intern() returns pooled String; new String creates new object [OK]

Common Mistakes:

• Assuming new String equals literal by ==
• Ignoring intern() effect on references
• Confusing == with .equals()