String comparison - Time & Space Complexity

Time Complexity: String comparison

O(n)

Understanding Time Complexity

When we compare two strings in C, we want to know how long it takes as the strings get longer.

We ask: How does the work grow when the strings grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int stringCompare(const char *str1, const char *str2) {
    int i = 0;
    while (str1[i] != '\0' && str2[i] != '\0') {
        if (str1[i] != str2[i]) {
            return str1[i] - str2[i];
        }
        i++;
    }
    return str1[i] - str2[i];
}
    

This code compares two strings character by character until it finds a difference or reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters one by one in a loop.
• How many times: Up to the length of the shorter string plus one (to check the terminating null character).

How Execution Grows With Input

As the strings get longer, the number of character checks grows roughly with the string length.

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 linearly as the strings get longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare grows in a straight line with the length of the strings.

Common Mistake

[X] Wrong: "String comparison always takes the same time no matter the string length."

[OK] Correct: The function checks characters one by one, so longer strings usually take more time.

Interview Connect

Understanding how string comparison time grows helps you write efficient code and explain your reasoning clearly in interviews.

Self-Check

"What if we stopped comparing as soon as we find the first difference? How would the time complexity change in the best case?"

Practice

1. Which function is used in C to compare the contents of two strings?

easy

A. strcpy

B. strlen

C. strcmp

D. strcat

Solution

1. Step 1: Identify string comparison functions

   Among the options, only strcmp is designed to compare two strings character by character.

2. Step 2: Understand other functions

   strcpy copies strings, strlen measures length, strcat concatenates strings; none compare contents.

3. Final Answer:

   strcmp -> Option C

4. Quick Check:

   strcmp compares strings [OK]

Hint: Use strcmp to compare strings, not == operator [OK]

Common Mistakes:

• Using == to compare strings
• Confusing strcpy with strcmp
• Assuming strlen compares strings

2. Which header file must be included to use the strcmp function in C?

easy

A.

B.

C.

D.

Solution

1. Step 1: Recall standard headers for string functions

   String functions like strcmp are declared in the <string.h> header file.

2. Step 2: Verify other headers

   <stdio.h> is for input/output, <stdlib.h> for general utilities, <ctype.h> for character handling, none provide strcmp.

3. Final Answer:

   <string.h> -> Option D

4. Quick Check:

   strcmp needs <string.h> [OK]

Hint: Include for strcmp and other string functions [OK]

Common Mistakes:

• Forgetting to include
• Including only
• Using wrong header like

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

#include <stdio.h>
#include <string.h>

int main() {
    char a[] = "apple";
    char b[] = "apricot";
    int result = strcmp(a, b);
    if (result < 0) {
        printf("a is less than b\n");
    } else if (result > 0) {
        printf("a is greater than b\n");
    } else {
        printf("a and b are equal\n");
    }
    return 0;
}

medium

A. a is less than b

B. a is greater than b

C. a and b are equal

D. Compilation error

Solution

1. Step 1: Understand strcmp result for "apple" and "apricot"

   strcmp compares strings lexicographically; "apple" is less than "apricot" because 'l' (in apple) comes before 'r' (in apricot).

2. Step 2: Check the if conditions

   Since result is negative, the program prints "a is less than b".

3. Final Answer:

   a is less than b -> Option A

4. Quick Check:

   strcmp("apple", "apricot") < 0 [OK]

Hint: strcmp returns negative if first string is lexically smaller [OK]

Common Mistakes:

• Assuming strcmp returns boolean
• Confusing lex order of 'l' and 'r'
• Expecting equality for different strings

4. Identify the error in this code snippet comparing two strings:

#include <stdio.h>
#include <string.h>

int main() {
    char str1[] = "hello";
    char str2[] = "hello";
    if (str1 == str2) {
        printf("Strings are equal\n");
    } else {
        printf("Strings are not equal\n");
    }
    return 0;
}

medium

A. Using '==' to compare strings instead of strcmp

B. Missing #include header

C. Incorrect printf format specifier

D. Strings are not initialized properly

Solution

1. Step 1: Understand string comparison in C

   Using '==' compares addresses, not string contents, so it does not check if strings are equal.

2. Step 2: Correct method to compare strings

   Use strcmp(str1, str2) == 0 to check if strings have the same content.

3. Final Answer:

   Using '==' to compare strings instead of strcmp -> Option A

4. Quick Check:

   Use strcmp for string content comparison [OK]

Hint: Never use '==' for strings; use strcmp instead [OK]

Common Mistakes:

• Using '==' operator for string comparison
• Ignoring string content vs pointer comparison
• Not including when using strcmp

5. You want to check if two strings str1 and str2 are equal ignoring case differences in C. Which approach correctly achieves this?

hard

A. Use strcmp(str1, str2) == 0

B. Use strcasecmp(str1, str2) == 0

C. Use strcmp(tolower(str1), tolower(str2)) == 0

D. Use strcmp(str1, str2) != 0

Solution

1. Step 1: Understand case-insensitive comparison

   strcmp compares case-sensitively, so it fails if cases differ. strcasecmp compares ignoring case.

2. Step 2: Evaluate other options

   Use strcmp(str1, str2) == 0 is case-sensitive; Use strcmp(tolower(str1), tolower(str2)) == 0 is invalid because tolower expects a char, not a string; Use strcmp(str1, str2) != 0 checks inequality, not equality.

3. Final Answer:

   Use strcasecmp(str1, str2) == 0 -> Option B

4. Quick Check:

   strcasecmp compares strings ignoring case [OK]

Hint: Use strcasecmp for case-insensitive string comparison [OK]

Common Mistakes:

• Using strcmp for case-insensitive check
• Applying tolower to whole strings incorrectly
• Confusing equality and inequality checks