String comparison (equals, compareTo) in Kotlin - Time & Space Complexity

Time Complexity: String comparison (equals, compareTo)

O(n)

Understanding Time Complexity

When we compare two strings in Kotlin, the time it takes depends on their length.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val str1 = "hello"
val str2 = "world"

// Check if strings are equal
val areEqual = str1.equals(str2)

// Compare strings lexicographically
val comparison = str1.compareTo(str2)
    

This code checks if two strings are the same and then compares their order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

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

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 with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare strings grows in a straight line as the strings get longer.

Common Mistake

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

[OK] Correct: The program 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 answer questions clearly.

Self-Check

"What if we compare strings that are always different in the first character? How would the time complexity change?"

Practice

1. Which Kotlin method should you use to check if two strings have exactly the same characters and case?
val a = "Hello"
val b = "hello"

easy

A. a.equals(b)

B. a.compareTo(b)

C. a === b

D. a.equals(b, ignoreCase = true)

Solution

1. Step 1: Understand equals() method

   The equals() method checks if two strings are exactly the same including case.

2. Step 2: Compare equals() with other options

   compareTo() returns an order number, === checks reference equality (not content), equals(ignoreCase=true) ignores case, so only equals() matches exact case-sensitive check.

3. Final Answer:

   a.equals(b) -> Option A

4. Quick Check:

   Use equals() for exact string match [OK]

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

Common Mistakes:

• Using compareTo() to check equality
• Assuming === checks content equality
• Using equals(ignoreCase=true) when case matters

2. Which of the following is the correct syntax to compare two strings str1 and str2 for equality ignoring case in Kotlin?

easy

A. str1.equals(str2, ignoreCase = true)

B. str1.compareTo(str2, ignoreCase = true)

C. str1.equals(str2)

D. str1 == str2

Solution

1. Step 1: Recall equals() with ignoreCase parameter

   In Kotlin, equals() can take ignoreCase=true to compare strings ignoring case differences.

2. Step 2: Check other options

   A: equals() without ignoreCase is case-sensitive, B: compareTo(ignoreCase=true) returns Int not Boolean, D: == is case-sensitive.

3. Final Answer:

   str1.equals(str2, ignoreCase = true) -> Option A

4. Quick Check:

   Use equals(ignoreCase=true) to ignore case [OK]

Hint: Use equals(ignoreCase=true) to compare ignoring case [OK]

Common Mistakes:

• Using compareTo(ignoreCase=true) directly (returns Int, not Boolean)
• Using == which is case-sensitive
• Forgetting to set ignoreCase=true

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

val s1 = "apple"
val s2 = "banana"
println(s1.compareTo(s2))

medium

A. A positive number

B. A negative number

C. 0

D. Compilation error

Solution

1. Step 1: Understand compareTo() behavior

   compareTo() returns a negative number if the first string is lexicographically less than the second.

2. Step 2: Compare "apple" and "banana" lex order

   "apple" comes before "banana" alphabetically, so compareTo returns a negative number.

3. Final Answer:

   A negative number -> Option B

4. Quick Check:

   "apple" < "banana" means compareTo() < 0 [OK]

Hint: compareTo() < 0 means first string is before second [OK]

Common Mistakes:

• Assuming compareTo() returns boolean
• Confusing positive and negative return values
• Thinking compareTo() returns 0 for different strings

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

val a = "Test"
val b = "test"
if (a.compareTo(b, ignoreCase = true)) {
    println("Equal")
} else {
    println("Not Equal")
}

medium

A. Missing parentheses in if condition

B. ignoreCase is not a valid parameter for compareTo()

C. Strings cannot be compared with compareTo()

D. compareTo() returns Int, cannot be used as Boolean

Solution

1. Step 1: Check compareTo() return type

   compareTo() returns an Int, not a Boolean, so it cannot be used directly in if condition.

2. Step 2: Understand how to check equality with compareTo()

   To check equality ignoring case, compareTo() == 0 should be used, not just compareTo() alone.

3. Final Answer:

   compareTo() returns Int, cannot be used as Boolean -> Option D

4. Quick Check:

   compareTo() returns Int, use == 0 to check equality [OK]

Hint: compareTo() returns Int; compare with 0 for equality [OK]

Common Mistakes:

• Using compareTo() directly as Boolean
• Forgetting to compare result with 0
• Assuming ignoreCase is invalid parameter (it is valid)

5. You want to sort a list of strings ignoring case in Kotlin. Which code snippet correctly sorts the list val fruits = listOf("Banana", "apple", "Cherry") ignoring case?

hard

A. fruits.sortedBy { it }

B. fruits.sortedBy(String.CASE_INSENSITIVE_ORDER)

C. fruits.sortedWith(String.CASE_INSENSITIVE_ORDER)

D. fruits.sorted()

Solution

1. Step 1: Understand sorting ignoring case

   To sort strings ignoring case, use a comparator that compares strings case-insensitively.

2. Step 2: Check options for case-insensitive sorting

   A and D are case-sensitive. C: sortedBy expects key selector, not Comparator (compile error). B uses built-in case-insensitive Comparator correctly.

3. Final Answer:

   fruits.sortedWith(String.CASE_INSENSITIVE_ORDER) -> Option C

4. Quick Check:

   Use sortedWith(String.CASE_INSENSITIVE_ORDER) for case-insensitive sort [OK]

Hint: Use sortedWith(String.CASE_INSENSITIVE_ORDER) to ignore case in sort [OK]

Common Mistakes:

• Using sorted() which is case-sensitive
• Using sortedBy { it } which is case-sensitive
• Confusing sortedBy (selector) with sortedWith (Comparator)