String handling basics in C++ - Time & Space Complexity

Time Complexity: String handling basics

O(n)

Understanding Time Complexity

When working with strings, it is important to know how the time to process them changes as the string gets longer.

We want to find out how the time to handle strings grows when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <string>
#include <iostream>

int countVowels(const std::string &s) {
    int count = 0;
    for (char c : s) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
            c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
            count++;
        }
    }
    return count;
}
    

This code counts how many vowels are in a given string by checking each character one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string.
• How many times: Once for every character in the string (n times).

How Execution Grows With Input

As the string gets longer, the number of characters to check grows the same way.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows directly with the length of the string.

Final Time Complexity

Time Complexity: O(n)

This means the time to count vowels grows in a straight line as the string gets longer.

Common Mistake

[X] Wrong: "Checking each character is very slow and grows faster than the string length."

[OK] Correct: Actually, the code looks at each character only once, so the time grows just as the string grows, not faster.

Interview Connect

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

Self-Check

"What if we changed the code to check every pair of characters instead of single characters? How would the time complexity change?"

Practice

1. What does the following C++ code do?
std::string s = "Hello";
int len = s.length();

easy

A. Changes the string s to "length"

B. Stores the length of the string "Hello" in variable len

C. Prints the string length to the screen

D. Deletes the string s

Solution

1. Step 1: Understand the string initialization

   The code creates a string variable s with the value "Hello".

2. Step 2: Understand the length() function

   The length() function returns the number of characters in the string, which is 5 for "Hello".

3. Final Answer:

   Stores the length of the string "Hello" in variable len -> Option B

4. Quick Check:

   string length = 5 [OK]

Hint: length() returns number of characters in a string [OK]

Common Mistakes:

• Thinking length() changes the string
• Confusing length() with printing
• Assuming length() deletes the string

2. Which of the following is the correct way to declare and initialize a string in C++?

easy

A. std::string s = "Hello";

B. string s = 'Hello';

C. char s = "Hello";

D. string s = Hello;

Solution

1. Step 1: Check string declaration syntax

   In C++, strings are declared using std::string and initialized with double quotes "".

2. Step 2: Analyze each option

   std::string s = "Hello"; uses std::string with double quotes correctly. string s = 'Hello'; uses single quotes which are for single characters. char s = "Hello"; uses char which holds one character, not a string. string s = Hello; misses quotes around Hello.

3. Final Answer:

   std::string s = "Hello"; -> Option A

4. Quick Check:

   Correct string syntax uses std::string and double quotes [OK]

Hint: Use std::string and double quotes for strings [OK]

Common Mistakes:

• Using single quotes for strings
• Using char for multiple characters
• Forgetting quotes around text

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

std::string s = "Hello";
char c = s[1];
std::cout << c << std::endl;

medium

A. o

B. H

C. l

D. e

Solution

1. Step 1: Understand string indexing

   Strings in C++ are zero-indexed, so s[0] = 'H', s[1] = 'e'.

2. Step 2: Identify the character at index 1

   The code stores s[1] in c, which is 'e', then prints it.

3. Final Answer:

   e -> Option D

4. Quick Check:

   Index 1 character = 'e' [OK]

Hint: Remember string indexing starts at 0 [OK]

Common Mistakes:

• Thinking indexing starts at 1
• Confusing characters at different positions
• Expecting the whole string instead of one char

4. Find the error in this code snippet:

std::string s = "Hello";
char c = s.at(5);
std::cout << c << std::endl;

medium

A. No error, prints 'o'

B. Compilation error: cannot assign char

C. Runtime error: out_of_range exception

D. Syntax error: wrong function name

Solution

1. Step 1: Check string length and indexing

   The string "Hello" has length 5, valid indices are 0 to 4.

2. Step 2: Understand s.at(5) behavior

   Accessing s.at(5) is out of range and throws a runtime exception.

3. Final Answer:

   Runtime error: out_of_range exception -> Option C

4. Quick Check:

   Accessing index 5 causes out_of_range error [OK]

Hint: s.at(index) throws error if index invalid [OK]

Common Mistakes:

• Assuming s.at() works like s[] without error
• Ignoring zero-based indexing
• Confusing syntax and runtime errors

5. Given a string std::string s = "apple,banana,cherry";, which code correctly extracts the substring "banana"?

hard

A. std::string sub = s.substr(6, 6);

B. std::string sub = s.substr(5, 6);

C. std::string sub = s.substr(6, 7);

D. std::string sub = s.substr(7, 6);

Solution

1. Step 1: Identify the start index of "banana"

   "apple," has 6 characters (indices 0 to 5), so 'b' starts at index 6.

2. Step 2: Determine length of "banana"

   "banana" has 6 characters.

3. Step 3: Use substr(start, length)

   Calling s.substr(6, 6) extracts 6 characters starting at index 6, which is "banana".

4. Final Answer:

   std::string sub = s.substr(6, 6); -> Option A

5. Quick Check:

   substr(6,6) = "banana" [OK]

Hint: Count start index and length carefully for substr() [OK]

Common Mistakes:

• Off-by-one errors in start index
• Wrong length parameter
• Confusing substr parameters order