How Strings Work Differently Across Languages in DSA C# - Complexity Walkthrough

Time Complexity: How Strings Work Differently Across Languages

O(n²)

Understanding Time Complexity

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

We want to see how string operations grow in cost as the string gets bigger in C#.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string s = "hello";
string result = "";
for (int i = 0; i < s.Length; i++)
{
    result += s[i];
}
Console.WriteLine(result);
    

This code builds a new string by adding one character at a time from the original string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding one character to the result string inside a loop.
• How many times: Once for each character in the original string (n times).

How Execution Grows With Input

Each time we add a character, a new string is created by copying the old one plus the new character.

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

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

Final Time Complexity

Time Complexity: O(n²)

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

Common Mistake

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

[OK] Correct: In C#, strings are immutable, so each addition creates a new string by copying all characters, making it slower than expected.

Interview Connect

Understanding how strings work under the hood 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. In C#, which of the following statements about strings is true?

easy

A. Strings are always stored in unmanaged memory.

B. Strings are mutable and can be changed directly after creation.

C. Strings are stored as arrays of characters that can be resized dynamically.

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

Solution

1. Step 1: Understand string immutability in C#

   In C#, strings are immutable, so any change creates a new string object.

2. Step 2: Compare options with C# string behavior

   Strings are immutable, meaning once created, they cannot be changed. correctly states immutability; others describe behaviors not true for C# strings.

3. Final Answer:

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

4. Quick Check:

   Immutable strings = Strings are immutable, meaning once created, they cannot be changed. [OK]

Hint: Remember: C# strings cannot be changed after creation [OK]

Common Mistakes:

• Thinking strings can be changed directly like arrays
• Confusing string mutability with StringBuilder
• Assuming strings are stored in unmanaged memory

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 = new string(hello);

Solution

1. Step 1: Check string literal syntax in C#

   Strings must be enclosed in double quotes " ". Single quotes are for chars.

2. Step 2: Validate each option

   string s = "hello"; uses double quotes correctly. string s = 'hello'; uses single quotes (wrong). string s = hello; misses quotes. string s = new string(hello); syntax is invalid.

3. Final Answer:

   string s = "hello"; -> Option A

4. Quick Check:

   Double quotes for strings = string s = "hello"; [OK]

Hint: Use double quotes "" for strings in C# [OK]

Common Mistakes:

• Using single quotes for strings
• Forgetting quotes around string literals
• Trying to use new string() with a string literal

3. What is the output of the following C# code?

string s1 = "hello";
string s2 = s1;
s2 = "world";
Console.WriteLine(s1);

medium

A. world

B. hello

C. null

D. Compilation error

Solution

1. Step 1: Understand string assignment and immutability

   s2 initially points to the same string as s1. Changing s2 to "world" creates a new string object for s2.

2. Step 2: Check what s1 points to after s2 changes

   s1 still points to "hello" because strings are immutable and s2 reassignment does not affect s1.

3. Final Answer:

   hello -> Option B

4. Quick Check:

   Immutable strings keep original value = hello [OK]

Hint: Changing one string variable doesn't affect another [OK]

Common Mistakes:

• Assuming s1 changes when s2 is reassigned
• Confusing string references with mutable objects
• Expecting runtime or compile errors

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

string s = "hello";
s[0] = 'H';
Console.WriteLine(s);

medium

A. Cannot assign to s[0] because strings are immutable.

B. Missing semicolon after string declaration.

C. Character literals must be in double quotes.

D. Console.WriteLine cannot print strings.

Solution

1. Step 1: Check string mutability and indexing

   Strings in C# are immutable; you cannot change characters by index.

2. Step 2: Validate other options

   Semicolons are present, character literals use single quotes correctly, Console.WriteLine can print strings.

3. Final Answer:

   Cannot assign to s[0] because strings are immutable. -> Option A

4. Quick Check:

   Strings immutable = cannot change characters by index [OK]

Hint: Strings cannot be changed by index in C# [OK]

Common Mistakes:

• Trying to modify string characters directly
• Confusing char and string literal syntax
• Assuming Console.WriteLine can't print strings

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

string s = "abc";
string t = s + "def";
string u = t.Replace('a', 'z');
Console.WriteLine(s);
Console.WriteLine(t);
Console.WriteLine(u);

hard

A. abc
def
zbcdef

B. abc
abcdef
abcdef

C. abc
abcdef
zbcdef

D. Compilation error due to Replace usage

Solution

1. Step 1: Analyze string concatenation

   t = s + "def" results in "abcdef".

2. Step 2: Analyze Replace method

   u = t.Replace('a', 'z') replaces 'a' with 'z' in "abcdef", resulting in "zbcdef".

3. Step 3: Check original strings remain unchanged

   s remains "abc" because strings are immutable.

4. Final Answer:

   abc abcdef zbcdef -> Option C

5. Quick Check:

   Immutable strings + Replace returns new string = abc abcdef zbcdef [OK]

Hint: Replace returns new string; originals stay same [OK]

Common Mistakes:

• Expecting Replace to change original string
• Confusing concatenation result
• Thinking Replace causes compile error