String functions overview in C++ - Time & Space Complexity

Time Complexity: String functions overview

O(n)

Understanding Time Complexity

When using string functions, it's important to know how their running time changes as the string gets longer.

We want to understand how the cost of these functions grows with the size of the input string.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <string>
#include <iostream>

int main() {
    std::string s = "hello world";
    auto length = s.length();
    auto pos = s.find('o');
    auto substr = s.substr(0, 5);
    s.append("!!!");
    std::cout << substr << std::endl;
    return 0;
}
    

This code uses common string functions: length, find, substr, and append.

Identify Repeating Operations

Look at what each function does repeatedly:

• length(): Checks the stored size, no loop.
• find(): Scans characters until it finds the target.
• substr(): Copies a part of the string, character by character.
• append(): Adds characters to the end, copying them.

The dominant operations are the ones that scan or copy characters.

How Execution Grows With Input

Let's see how the number of operations changes as the string size grows.

Input Size (n)	Approx. Operations for find()	Approx. Operations for substr()
10	Up to 10 checks	Copies up to 5 chars
100	Up to 100 checks	Copies up to 5 chars
1000	Up to 1000 checks	Copies up to 5 chars

Notice that find() grows with the string length, but substr() depends on the substring size, not the whole string.

Final Time Complexity

Time Complexity: O(n)

This means the time to run these string functions grows roughly in direct proportion to the string length.

Common Mistake

[X] Wrong: "All string functions run in constant time regardless of string size."

[OK] Correct: Some functions like find() need to look at many characters, so their time grows with string length. substr() time grows with the substring size.

Interview Connect

Understanding how string functions scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we changed substr() to copy the entire string instead of a part? How would the time complexity change?"

Practice

1. Which C++ string function returns the number of characters in a string?

easy

A. substr()

B. append()

C. length()

D. find()

Solution

1. Step 1: Understand string length function

   The length() function returns how many characters are in the string.

2. Step 2: Compare with other functions

   append() adds text, substr() extracts part, find() searches for text.

3. Final Answer:

   length() -> Option C

4. Quick Check:

   String length = length() [OK]

Hint: Length means count characters, use length() [OK]

Common Mistakes:

• Confusing length() with append()
• Using substr() to get length
• Thinking find() returns length

2. Which of the following is the correct syntax to add " world" to a string str in C++?

easy

A. str.append(" world");

B. str.add(" world");

C. str.concat(" world");

D. str.push_back(" world");

Solution

1. Step 1: Identify correct append syntax

   In C++, append() adds text to the end of a string: str.append(" world");.

2. Step 2: Check other options

   add() and concat() are not string methods in C++. push_back() adds a single character, not a string.

3. Final Answer:

   str.append(" world"); -> Option A

4. Quick Check:

   Use append() to add text [OK]

Hint: Use append() to add text, not add() or concat() [OK]

Common Mistakes:

• Using add() or concat() which don't exist
• Using push_back() with string argument
• Missing semicolon at end

3. What is the output of this C++ code?

std::string s = "hello world";
std::cout << s.substr(6, 5);

medium

A. worlds

B. hello

C. hello world

D. world

Solution

1. Step 1: Understand substr parameters

   substr(6, 5) means start at index 6 and take 5 characters.

2. Step 2: Extract substring from "hello world"

   Index 6 is 'w', next 5 characters are "world".

3. Final Answer:

   world -> Option D

4. Quick Check:

   substr(6,5) = "world" [OK]

Hint: Count from zero, substr(start, length) extracts text [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Taking wrong number of characters
• Confusing substr with find

4. Identify the error in this C++ code snippet:

std::string s = "example";
s = s.substr(3, 10);

medium

A. substr length exceeds string length but no error occurs

B. substr start index is invalid

C. substr requires two arguments but only one given

D. Cannot assign substr result to string variable

Solution

1. Step 1: Check substr parameters

   Start index 3 is valid. Length 10 is longer than remaining string length.

2. Step 2: Understand substr behavior with long length

   substr returns substring from index 3 to end without error even if length is too big.

3. Final Answer:

   substr length exceeds string length but no error occurs -> Option A

4. Quick Check:

   substr handles long length safely [OK]

Hint: substr length can be longer than string safely [OK]

Common Mistakes:

• Expecting runtime error for long length
• Thinking start index is invalid
• Confusing substr arguments count

5. Given a string text = "Hello C++ World", which code snippet converts it to all uppercase letters?

hard

A. text.toUpperCase();

B. for (auto &c : text) c = toupper(c);

C. text.upper();

D. transform(text.begin(), text.end(), text.begin(), tolower);

Solution

1. Step 1: Identify correct uppercase conversion

   Looping over each character and applying toupper() converts all letters to uppercase.

2. Step 2: Check other options

   toUpperCase() and upper() are not C++ string methods. transform(text.begin(), text.end(), text.begin(), tolower); uses tolower which converts to lowercase.

3. Final Answer:

   for (auto &c : text) c = toupper(c); -> Option B

4. Quick Check:

   Use loop + toupper() for uppercase [OK]

Hint: Use loop with toupper() to change case [OK]

Common Mistakes:

• Using non-existent string methods
• Using tolower instead of toupper
• Not using reference in loop to modify string