String type and immutability in Kotlin - Time & Space Complexity

Time Complexity: String type and immutability

O(n²)

Understanding Time Complexity

We want to understand how working with strings affects the time it takes for a program to run.

Specifically, how does changing or combining strings grow in cost as the strings get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun buildString(n: Int): String {
    var result = ""
    for (i in 1..n) {
        result += "a"
    }
    return result
}

This code creates a string by adding the letter "a" one by one, n times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding a character to the string inside the loop.
• How many times: The loop runs n times, each time creating a new string.

How Execution Grows With Input

Each time we add a character, the program copies the whole string so far and adds one more character.

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

Pattern observation: The work grows much faster than n; 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 the whole string again.

Common Mistake

[X] Wrong: "Adding one character to a string inside a loop takes the same time no matter how long the string is."

[OK] Correct: Strings are immutable, so each addition makes a new string by copying all characters, which takes more time as the string grows.

Interview Connect

Understanding how string operations grow helps you write code that runs faster and avoids surprises in real projects.

Self-Check

What if we used a StringBuilder instead of adding characters directly? How would the time complexity change?

Practice

1. What does it mean that a String in Kotlin is immutable?

easy

A. Strings can only hold numbers, not letters.

B. You can change characters inside the String directly.

C. Once created, the text inside a String cannot be changed.

D. Strings automatically update when variables change.

Solution

1. Step 1: Understand immutability concept

   Immutability means the object cannot be changed after creation.

2. Step 2: Apply to Kotlin String

   Kotlin Strings cannot be modified once created; any change creates a new String.

3. Final Answer:

   Once created, the text inside a String cannot be changed. -> Option C

4. Quick Check:

   String immutability = cannot change text [OK]

Hint: Remember: Strings are like printed paper, not editable [OK]

Common Mistakes:

• Thinking you can change characters inside the same String
• Confusing immutability with variable reassignment
• Believing Strings hold only numbers

2. Which of the following is the correct way to concatenate two Strings str1 and str2 in Kotlin?

easy

A. str1 & str2

B. str1 + str2

C. str1.join(str2)

D. str1.append(str2)

Solution

1. Step 1: Recall Kotlin String concatenation syntax

   Kotlin uses the + operator to join two Strings.

2. Step 2: Check each option

   Only str1 + str2 is valid Kotlin syntax for concatenation.

3. Final Answer:

   str1 + str2 -> Option B

4. Quick Check:

   Use + to join Strings [OK]

Hint: Use + to combine Strings, like adding words together [OK]

Common Mistakes:

• Using methods like append or join which don't exist on Kotlin String
• Using & which is not a Kotlin operator for Strings
• Trying to modify Strings directly

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

val text = "Hello"
val newText = text + " World"
println(text)

medium

A. Hello

B. Hello World

C. World

D. HelloWorld

Solution

1. Step 1: Understand String immutability and concatenation

   The original String text remains unchanged after concatenation.

2. Step 2: Analyze the print statement

   Only text is printed, which is still "Hello".

3. Final Answer:

   Hello -> Option A

4. Quick Check:

   Original String unchanged = Hello [OK]

Hint: Printing original String shows it stays the same [OK]

Common Mistakes:

• Assuming original String changes after + operation
• Confusing newText with text in print
• Ignoring immutability of Strings

4. Identify the error in this Kotlin code snippet:

var greeting = "Hi"
greeting[0] = 'B'
println(greeting)

medium

A. println cannot print Strings.

B. Variable greeting should be val, not var.

C. Single quotes cannot be used for characters.

D. You cannot change characters in a String by index.

Solution

1. Step 1: Check String mutability rules

   Kotlin Strings are immutable; you cannot assign to an index.

2. Step 2: Analyze the code line causing error

   Line greeting[0] = 'B' tries to change a character, which is invalid.

3. Final Answer:

   You cannot change characters in a String by index. -> Option D

4. Quick Check:

   Strings immutable = no index assignment [OK]

Hint: Strings are like frozen text, can't change letters inside [OK]

Common Mistakes:

• Thinking var allows character change inside String
• Confusing char literals with strings
• Believing println can't print Strings

5. Given a list of words, how can you create a new list with each word appended by "!" without changing the original words?

val words = listOf("cat", "dog", "bird")
val excitedWords = ???

Which Kotlin code correctly does this considering String immutability?

hard

A. val excitedWords = words.map { it + "!" }

B. val excitedWords = words.apply { this[0] += "!" }

C. val excitedWords = words.forEach { it + "!" }

D. val excitedWords = words.replace("", "!")

Solution

1. Step 1: Understand immutability and list transformations

   Strings cannot be changed, so create new Strings with + "!".

2. Step 2: Use map to transform each word into a new String

   map returns a new list with transformed elements without modifying original.

3. Final Answer:

   val excitedWords = words.map { it + "!" } -> Option A

4. Quick Check:

   Use map + + operator for new list [OK]

Hint: Use map to create new list with modified Strings [OK]

Common Mistakes:

• Trying to modify list elements directly with apply or forEach
• Using replace on list instead of Strings
• Assuming original list changes