nchar and substring in R Programming - Time & Space Complexity

Time Complexity: nchar and substring

O(n)

Understanding Time Complexity

We want to understand how the time it takes to use nchar and substring changes as the size of the text grows.

How does the length of the string affect the work these functions do?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text <- "Hello, world!"
length_text <- nchar(text)
part_text <- substring(text, 1, 5)
print(length_text)
print(part_text)

This code finds the length of a string and extracts a part of it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Counting characters in the string for nchar, and copying characters for substring.
• How many times: Each character is checked once for nchar, and the substring copies characters once for the requested range.

How Execution Grows With Input

As the string gets longer, nchar checks more characters, and substring copies more characters if the substring length grows.

Input Size (n)	Approx. Operations
10	About 10 checks for nchar, up to 5 copies for substring
100	About 100 checks, up to 100 copies
1000	About 1000 checks, up to 1000 copies

Pattern observation: The work grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows linearly with the length of the string.

Common Mistake

[X] Wrong: "nchar and substring run instantly no matter how long the string is."

[OK] Correct: Both functions must look at characters to count or copy them, so longer strings take more time.

Interview Connect

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

Self-Check

"What if we used substring to extract a fixed small part regardless of string length? How would the time complexity change?"

Practice

1. What does the nchar function do in R?

easy

A. Returns the number of characters in a string

B. Extracts a substring from a string

C. Converts a string to uppercase

D. Counts the number of words in a string

Solution

1. Step 1: Understand the purpose of nchar

   The nchar function counts how many characters are in a string, including spaces and punctuation.

2. Step 2: Compare with other options

   Other options describe different functions: substring extracts parts, toupper converts case, and word count is not done by nchar.

3. Final Answer:

   Returns the number of characters in a string -> Option A

4. Quick Check:

   nchar("hello") = 5 [OK]

Hint: Remember: nchar counts characters, substring extracts parts [OK]

Common Mistakes:

• Confusing nchar with substring
• Thinking nchar counts words
• Assuming nchar changes the string

2. Which of the following is the correct way to extract the substring "cat" from the string "concatenate" in R?

easy

A. substring("concatenate", 3, 5)

B. substring("concatenate", 4, 6)

C. substring("concatenate", 5, 7)

D. substring("concatenate", 2, 4)

Solution

1. Step 1: Identify the position of "cat" in "concatenate"

   "concatenate" is c(1)o(2)n(3)c(4)a(5)t(6)e(7)n(8)a(9)t(10)e(11). The substring "cat" starts at position 4 and ends at 6.

2. Step 2: Use substring with correct start and end

   Using substring("concatenate", 4, 6) extracts characters 4 to 6, which is "cat".

3. Final Answer:

   substring("concatenate", 4, 6) -> Option B

4. Quick Check:

   substring("concatenate", 4, 6) = "cat" [OK]

Hint: Count characters starting at 1 to find substring positions [OK]

Common Mistakes:

• Starting count at 0 instead of 1
• Mixing up start and end positions
• Using incorrect substring indices

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

text <- "Programming"
len <- nchar(text)
sub <- substring(text, 4, 7)
print(len)
print(sub)

medium

A. 11 and "gram"

B. 11 and "gramm"

C. 10 and "gram"

D. 10 and "gramm"

Solution

1. Step 1: Calculate length of "Programming" using nchar

   "Programming" has 11 characters: P(1) r(2) o(3) g(4) r(5) a(6) m(7) m(8) i(9) n(10) g(11). So, len = 11.

2. Step 2: Extract substring from position 4 to 7

   Characters 4 to 7 are g(4) r(5) a(6) m(7), so substring is "gram".

3. Final Answer:

   11 and "gram" -> Option A

4. Quick Check:

   nchar("Programming") = 11, substring(4,7) = "gram" [OK]

Hint: Count characters carefully; substring includes both start and end [OK]

Common Mistakes:

• Counting length as 10 instead of 11
• Extracting one extra character in substring
• Confusing substring end position as exclusive

4. The following code is intended to extract "data" from the string "database" but it gives wrong output. What is the error?

text <- "database"
result <- substring(text, 1, 3)
print(result)

medium

A. The string variable is misspelled

B. substring function syntax is wrong

C. nchar should be used instead of substring

D. Start and end positions are incorrect; should be 1 to 4

Solution

1. Step 1: Check the substring positions used

   substring(text, 1, 3) extracts characters 1 to 3: "dat" from "database".

2. Step 2: Identify correct positions for "data"

   "data" is characters 1 to 4, so end position should be 4, not 3.

3. Final Answer:

   Start and end positions are incorrect; should be 1 to 4 -> Option D

4. Quick Check:

   substring("database", 1, 4) = "data" [OK]

Hint: Remember substring end position is inclusive [OK]

Common Mistakes:

• Using end position one less than needed
• Confusing substring with nchar usage
• Assuming substring excludes end position

5. You have a vector of strings: words <- c("apple", "banana", "cherry"). Write R code using substring and nchar to create a new vector containing the last 3 characters of each word. Which code snippet does this correctly?

hard

A. substring(words, nchar(words), nchar(words)+2)

B. substring(words, 1, 3)

C. substring(words, nchar(words)-2, nchar(words))

D. substring(words, nchar(words)-3, nchar(words)-1)

Solution

1. Step 1: Understand how to get last 3 characters

   For each word, last 3 characters start at position (length - 2) and end at length. Use nchar(words) to get length.

2. Step 2: Use substring with vectorized start and end

   substring(words, nchar(words)-2, nchar(words)) extracts last 3 characters for each word correctly.

3. Step 3: Check other options

   substring(words, 1, 3) extracts first 3 characters, C uses invalid end position, D extracts wrong positions.

4. Final Answer:

   substring(words, nchar(words)-2, nchar(words)) -> Option C

5. Quick Check:

   Last 3 chars of "banana" = "ana" [OK]

Hint: Use nchar(word)-2 as start for last 3 chars [OK]

Common Mistakes:

• Using fixed start positions instead of dynamic
• Off-by-one errors in start or end positions
• Assuming substring end is exclusive