String comparison and equality in C Sharp (C#) - Time & Space Complexity

Time Complexity: String comparison and equality

O(n)

Understanding Time Complexity

When comparing two strings, the time it takes depends on their length and content.

We want to know how the work grows as strings get longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string s1 = "hello world";
string s2 = "hello there";
bool areEqual = s1.Equals(s2);

This code checks if two strings are exactly the same.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters one by one in both strings.
• How many times: Up to the length of the shorter string, or until a difference is found.

How Execution Grows With Input

As strings get longer, the comparison checks more characters.

Input Size (n)	Approx. Operations
10	Up to 10 character comparisons
100	Up to 100 character comparisons
1000	Up to 1000 character comparisons

Pattern observation: The work grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare grows linearly with the length of the strings.

Common Mistake

[X] Wrong: "Comparing two strings always takes the same time regardless of their content."

[OK] Correct: The comparison stops early if a difference is found, so shorter matches can be faster.

Interview Connect

Understanding how string comparison scales helps you reason about performance in many programs.

Self-Check

"What if we compare strings ignoring case? How would the time complexity change?"

Practice

1. Which of the following is the correct way to check if two strings str1 and str2 have the same value in C#?

easy

A. if (str1 == str2)

B. if (str1 = str2)

C. if (str1.Equals)

D. if (str1.CompareTo(str2))

Solution

1. Step 1: Understand string equality operator

   In C#, == compares the values of two strings correctly.

2. Step 2: Analyze other options

   str1 = str2 is assignment, str1.Equals is incomplete, and CompareTo returns an int, not a bool.

3. Final Answer:

   if (str1 == str2) -> Option A

4. Quick Check:

   Use == for string equality [OK]

Hint: Use == to compare string values directly [OK]

Common Mistakes:

• Using single = instead of ==
• Calling Equals without parentheses or arguments
• Using CompareTo expecting a boolean

2. Which of the following is the correct syntax to compare two strings a and b ignoring case in C#?

easy

A. a.Equals(b)

B. a == b.ToLower()

C. string.Equals(a, b, StringComparison.OrdinalIgnoreCase)

D. string.Compare(a, b)

Solution

1. Step 1: Identify case-insensitive comparison method

   string.Equals with StringComparison.OrdinalIgnoreCase compares strings ignoring case.

2. Step 2: Check other options

   a == b.ToLower() compares different types, a.Equals(b) is case-sensitive, and string.Compare returns int, not bool.

3. Final Answer:

   string.Equals(a, b, StringComparison.OrdinalIgnoreCase) -> Option C

4. Quick Check:

   Use string.Equals with OrdinalIgnoreCase for case-insensitive [OK]

Hint: Use string.Equals with OrdinalIgnoreCase to ignore case [OK]

Common Mistakes:

• Using == which is case-sensitive
• Calling Equals without StringComparison argument
• Using string.Compare expecting boolean

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

string s1 = "apple";
string s2 = "Banana";
int result = string.Compare(s1, s2, StringComparison.OrdinalIgnoreCase);
Console.WriteLine(result);

medium

A. -1

B. 0

C. 1

D. Compilation error

Solution

1. Step 1: Understand string.Compare with OrdinalIgnoreCase

   It compares strings ignoring case and returns negative if first is before second alphabetically.

2. Step 2: Compare "apple" and "Banana" ignoring case

   "apple" comes before "banana" alphabetically, so result is negative (-1).

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   "apple" < "Banana" ignoring case = -1 [OK]

Hint: Compare returns negative if first string is alphabetically before second [OK]

Common Mistakes:

• Assuming Compare returns boolean
• Ignoring case sensitivity in comparison
• Expecting 0 when strings differ

4. The following code is intended to check if two strings are equal ignoring case, but it does not work as expected. What is the error?

string a = "Hello";
string b = "hello";
if (a == b.ToLower())
{
    Console.WriteLine("Equal");
} else {
    Console.WriteLine("Not Equal");
}

medium

A. The code should use 'string.Compare(a, b)' without ToLower()

B. b.ToLower() returns null, causing error

C. The code should use 'a.Equals(b)' instead

D. Using '==' compares case-sensitively, so it fails here

Solution

1. Step 1: Analyze '==' operator behavior

   The '==' operator compares strings case-sensitively, so "Hello" != "hello".

2. Step 2: Understand why ToLower() doesn't fix it

   Comparing 'a' to 'b.ToLower()' still compares case-sensitively; 'a' is "Hello" (mixed case), so comparison fails.

3. Final Answer:

   Using '==' compares case-sensitively, so it fails here -> Option D

4. Quick Check:

   '==' is case-sensitive, so this check fails [OK]

Hint: Use string.Equals with ignore case instead of == [OK]

Common Mistakes:

• Assuming ToLower() changes original string
• Using == for case-insensitive comparison
• Not calling Equals with StringComparison argument

5. You want to sort a list of strings alphabetically ignoring case in C#. Which approach correctly compares two strings x and y inside a custom comparer?

hard

A. return x == y ? 0 : 1;

B. return string.Compare(x, y, StringComparison.OrdinalIgnoreCase);

C. return x.Equals(y) ? 0 : -1;

D. return x.CompareTo(y);

Solution

1. Step 1: Understand sorting comparer requirements

   A comparer must return negative, zero, or positive int based on alphabetical order.

2. Step 2: Check each option's return value and case sensitivity

   return string.Compare(x, y, StringComparison.OrdinalIgnoreCase); uses string.Compare with OrdinalIgnoreCase, correctly returning int for sorting ignoring case. return x == y ? 0 : 1; returns only 0 or 1, not suitable. return x.Equals(y) ? 0 : -1; returns 0 or -1 but ignores order and case. return x.CompareTo(y); uses CompareTo which is case-sensitive.

3. Final Answer:

   return string.Compare(x, y, StringComparison.OrdinalIgnoreCase); -> Option B

4. Quick Check:

   Use string.Compare with OrdinalIgnoreCase for case-insensitive sorting [OK]

Hint: Use string.Compare with OrdinalIgnoreCase in sorting comparer [OK]

Common Mistakes:

• Returning only 0 or 1 instead of negative/zero/positive
• Using case-sensitive CompareTo for ignoring case
• Using Equals which returns bool, not int