String comparison in Java - Time & Space Complexity

Time Complexity: String comparison

O(n)

Understanding Time Complexity

When we compare two strings, the time it takes depends on their length. We want to understand how this time grows as the strings get longer.

How does the number of steps change when comparing bigger strings?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public boolean compareStrings(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }
    for (int i = 0; i < a.length(); i++) {
        if (a.charAt(i) != b.charAt(i)) {
            return false;
        }
    }
    return true;
}
    

This code checks if two strings are exactly the same by comparing each character one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop comparing characters at each position.
• How many times: Up to the length of the strings (n times).

How Execution Grows With Input

As the strings get longer, the number of character comparisons grows roughly the same as the string length.

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

Pattern observation: The work grows in a straight line with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare two strings grows directly with their length.

Common Mistake

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

[OK] Correct: The comparison checks each character until a difference is found or the end is reached, 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 used a method that compares only the first few characters? How would the time complexity change?"

Practice

1. Which method should you use in Java to check if two strings have exactly the same characters and case?
String s1 = "Hello";
String s2 = "hello";

easy

A. s1 == s2

B. s1.compareTo(s2)

C. s1.equalsIgnoreCase(s2)

D. s1.equals(s2)

Solution

1. Step 1: Understand string equality in Java

   Using == compares references, not content, so it is not reliable for string content comparison.

2. Step 2: Choose the method for exact match including case

   equals() checks if two strings have exactly the same characters and case, which is what is asked.

3. Final Answer:

   s1.equals(s2) -> Option D

4. Quick Check:

   Use equals() for exact string match [OK]

Hint: Use equals() for exact string match including case [OK]

Common Mistakes:

• Using == instead of equals() for string content comparison
• Using equalsIgnoreCase() when case matters
• Using compareTo() for equality check

2. Which of the following is the correct syntax to compare two strings s1 and s2 ignoring case in Java?

easy

A. s1.compareToIgnoreCase(s2)

B. s1.equals(s2)

C. s1.equalsIgnoreCase(s2)

D. s1 == s2

Solution

1. Step 1: Identify method to compare strings ignoring case

   Java provides equalsIgnoreCase() to compare strings ignoring letter case differences.

2. Step 2: Confirm syntax correctness

   s1.equalsIgnoreCase(s2) is the correct method call syntax.

3. Final Answer:

   s1.equalsIgnoreCase(s2) -> Option C

4. Quick Check:

   Use equalsIgnoreCase() to ignore case in string comparison [OK]

Hint: Use equalsIgnoreCase() to compare strings ignoring case [OK]

Common Mistakes:

• Using equals() when ignoring case is needed
• Using == for string comparison
• Using non-existent compareToIgnoreCase() method

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

String a = "apple";
String b = "banana";
int result = a.compareTo(b);
System.out.println(result > 0 ? "a > b" : "a <= b");

medium

A. a > b

B. a <= b

C. 0

D. Compilation error

Solution

1. Step 1: Understand compareTo() behavior

   compareTo() returns a negative number if the first string is alphabetically before the second.

2. Step 2: Compare "apple" and "banana" alphabetically

   "apple" comes before "banana", so a.compareTo(b) returns a negative value, making result > 0 false.

3. Final Answer:

   a <= b -> Option B

4. Quick Check:

   compareTo() negative means first string is less [OK]

Hint: compareTo() negative means first string is alphabetically before second [OK]

Common Mistakes:

• Assuming compareTo() returns boolean
• Confusing positive and negative return values
• Expecting 0 when strings differ

4. The following code is intended to print "Strings are equal" if two strings match ignoring case. What is wrong?

String s1 = "Java";
String s2 = "java";
if (s1 == s2) {
    System.out.println("Strings are equal");
} else {
    System.out.println("Strings are not equal");
}

medium

A. Using == compares references, not content

B. Missing semicolon after if condition

C. Strings cannot be compared in Java

D. Should use compareTo() instead of ==

Solution

1. Step 1: Identify how string comparison works

   Using == compares if both variables point to the same object, not if their text is equal.

2. Step 2: Correct way to compare ignoring case

   Use s1.equalsIgnoreCase(s2) to compare string content ignoring case.

3. Final Answer:

   Using == compares references, not content -> Option A

4. Quick Check:

   Use equalsIgnoreCase() for content ignoring case [OK]

Hint: Never use == for string content comparison [OK]

Common Mistakes:

• Using == instead of equalsIgnoreCase()
• Thinking == compares string content
• Using compareTo() for equality check

5. You want to sort an array of strings alphabetically ignoring case. Which approach correctly compares two strings s1 and s2 for sorting?

hard

A. s1.compareToIgnoreCase(s2)

B. s1.equalsIgnoreCase(s2)

C. s1.compareTo(s2)

D. s1 == s2

Solution

1. Step 1: Understand sorting with string comparison

   Sorting requires a method that returns an integer indicating order, not just equality.

2. Step 2: Identify method ignoring case for order

   compareToIgnoreCase() compares strings alphabetically ignoring case and returns an int for sorting.

3. Step 3: Confirm method availability

   Java's String class has compareToIgnoreCase() for this purpose.

4. Final Answer:

   s1.compareToIgnoreCase(s2) -> Option A

5. Quick Check:

   Use compareToIgnoreCase() for case-insensitive sorting [OK]

Hint: Use compareToIgnoreCase() to sort strings ignoring case [OK]

Common Mistakes:

• Using equalsIgnoreCase() which returns boolean, not order
• Using compareTo() which is case sensitive
• Using == which compares references