String Basics and Memory Representation in DSA C# - 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.

string CopyString(string input)
{
    string copy = "";
    for (int i = 0; i < input.Length; i++)
    {
        copy += input[i];
    }
    return copy;
}
    

This code creates a copy of the input string by adding each character one by one.

Identify Repeating Operations

• Primary operation: Looping through each character of the input string.
• How many times: Exactly once for each character, so as many times as the string length.

How Execution Grows With Input

As the string gets longer, the number of steps grows more than just the length because adding to a string inside a loop creates new strings each time.

Input Size (n)	Approx. Operations
10	About 55 operations
100	About 5,050 operations
1000	About 500,500 operations

Pattern observation: The operations grow roughly with the square of the string length because each addition copies the whole string so far.

Final Time Complexity

Time Complexity: O(n²)

This means the time to copy the string grows very quickly as the string gets longer, because each step copies more characters.

Common Mistake

[X] Wrong: "Adding characters one by one to a string inside a loop is fast and takes linear time."

[OK] Correct: Each addition creates a new string by copying all characters so far, making the total work grow much faster than the string length.

Interview Connect

Understanding how string operations cost time helps you write efficient code and explain your choices clearly in interviews.

Self-Check

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

Practice

1. What does the string type in C# represent in memory?

easy

A. A list of integers representing ASCII codes

B. A sequence of characters stored as Unicode values

C. A mutable array of bytes

D. A pointer to a memory address without data

Solution

1. Step 1: Understand string storage in C#

   C# strings store characters as Unicode, allowing international text.

2. Step 2: Compare options with string behavior

   Only A sequence of characters stored as Unicode values correctly describes strings as sequences of Unicode characters.

3. Final Answer:

   A sequence of characters stored as Unicode values -> Option B

4. Quick Check:

   string = Unicode characters [OK]

Hint: Remember C# strings are Unicode sequences, not byte arrays [OK]

Common Mistakes:

• Thinking strings are mutable arrays
• Confusing ASCII with Unicode
• Assuming strings are just pointers

2. Which of the following is the correct way to declare and initialize a string in C#?

easy

A. string s = "hello";

B. string s = hello;

C. string s = 'hello';

D. string s = "hello";
char[] arr = s;

Solution

1. Step 1: Check string literal syntax

   In C#, string literals use double quotes, so "hello" is correct.

2. Step 2: Validate each option

   string s = 'hello'; uses single quotes (for chars), B misses quotes, D tries to assign string to char array directly (invalid).

3. Final Answer:

   string s = "hello"; -> Option A

4. Quick Check:

   Strings use double quotes in C# [OK]

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

Common Mistakes:

• Using single quotes for strings
• Forgetting quotes around text
• Assigning string directly to char array

3. What will be the output of the following C# code?

string s1 = "hello";
string s2 = "hello";
Console.WriteLine(object.ReferenceEquals(s1, s2));

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand string interning in C#

   String literals with same content are interned and share the same reference.

2. Step 2: Check ReferenceEquals for s1 and s2

   Since both are "hello" literals, ReferenceEquals returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   String literals share references = true [OK]

Hint: String literals with same text share references [OK]

Common Mistakes:

• Assuming ReferenceEquals returns false for equal strings
• Confusing value equality with reference equality
• Expecting runtime errors

4. Identify the error in the following C# code snippet:

string s = "test";
s[0] = 'T';
Console.WriteLine(s);

medium

A. Runtime error: index out of range

B. Syntax error: missing semicolon

C. Strings are immutable; cannot assign to s[0]

D. No error; output is "Test"

Solution

1. Step 1: Check string mutability in C#

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

2. Step 2: Analyze assignment to s[0]

   Assigning to s[0] causes a compile-time error because strings cannot be modified this way.

3. Final Answer:

   Strings are immutable; cannot assign to s[0] -> Option C

4. Quick Check:

   Strings immutable = assignment error [OK]

Hint: Remember strings cannot be changed character-by-character [OK]

Common Mistakes:

• Trying to modify string characters directly
• Expecting runtime error instead of compile error
• Assuming strings behave like char arrays

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

string s = "hello";
string t = s + " world";
Console.WriteLine(s);
Console.WriteLine(t);

Choose the correct output representation.

hard

A. hello world
hello

B. hello world
hello world

C. hello
world

D. hello
hello world

Solution

1. Step 1: Understand string concatenation and immutability

   Concatenation creates a new string; original string s remains unchanged.

2. Step 2: Trace the output statements

   Console.WriteLine(s) prints hello; Console.WriteLine(t) prints hello world.

3. Final Answer:

   hello hello world -> Option D

4. Quick Check:

   Original string unchanged, new string created [OK]

Hint: Concatenation creates new string; original stays same [OK]

Common Mistakes:

• Assuming original string changes after concatenation
• Mixing order of printed strings
• Confusing string references with values