Gsub and sub for replacement in Ruby - Time & Space Complexity

Time Complexity: Gsub and sub for replacement

O(n)

Understanding Time Complexity

When we use sub or gsub in Ruby, we want to know how the time to replace text grows as the text gets longer.

We ask: How does the work change when the input string grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello hello hello"
result_sub = text.sub("hello", "hi")
result_gsub = text.gsub("hello", "hi")
    

This code replaces the first occurrence of "hello" with "hi" using sub, and all occurrences using gsub.

Identify Repeating Operations

Look at what repeats when replacing text:

• Primary operation: Scanning the string to find matches of the target text.
• How many times: For sub, it stops after the first match; for gsub, it continues scanning the whole string to replace all matches.

How Execution Grows With Input

As the string gets longer, the time to scan grows roughly with the string length.

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

Pattern observation: The work grows in a straight line as the string gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to replace text grows directly with the length of the string.

Common Mistake

[X] Wrong: "gsub is always much slower than sub because it replaces all matches."

[OK] Correct: Both scan the string, but gsub continues scanning after the first match, so the difference depends on how many matches there are, not just the method itself.

Interview Connect

Understanding how string replacement scales helps you write efficient code and explain your choices clearly in real projects or interviews.

Self-Check

What if we used a regular expression with gsub instead of a simple string? How would the time complexity change?

Practice

1. What is the main difference between sub and gsub methods in Ruby?

easy

A. sub replaces all matches, gsub replaces only the first match.

B. sub replaces only the first match, gsub replaces all matches.

C. sub deletes matches, gsub adds new text.

D. sub works only on arrays, gsub works on strings.

Solution

1. Step 1: Understand sub behavior

   sub replaces only the first occurrence of the pattern in the string.

2. Step 2: Understand gsub behavior

   gsub replaces all occurrences of the pattern in the string.

3. Final Answer:

   sub replaces only the first match, gsub replaces all matches. -> Option B

4. Quick Check:

   sub = first match, gsub = all matches [OK]

Hint: Remember: sub = single replace, gsub = global replace [OK]

Common Mistakes:

• Confusing which method replaces all matches
• Thinking sub works on arrays
• Believing gsub replaces only one match

2. Which of the following is the correct syntax to replace the first occurrence of 'cat' with 'dog' in the string "cat and cat" using sub?

easy

A. "cat and cat".substitute('cat', 'dog')

B. "cat and cat".gsub('cat', 'dog')

C. "cat and cat".replace('cat', 'dog')

D. "cat and cat".sub('cat', 'dog')

Solution

1. Step 1: Identify correct method for first occurrence replacement

   sub replaces only the first match, so it is the correct method here.

2. Step 2: Check method syntax

   The syntax is string.sub(pattern, replacement), so "cat and cat".sub('cat', 'dog') is correct.

3. Final Answer:

   "cat and cat".sub('cat', 'dog') -> Option D

4. Quick Check:

   sub syntax = string.sub(pattern, replacement) [OK]

Hint: Use sub for first match: string.sub('old', 'new') [OK]

Common Mistakes:

• Using gsub instead of sub for first occurrence
• Using non-existent methods like replace or substitute
• Wrong method call syntax

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

text = "hello hello hello"
result = text.sub('hello', 'hi')
puts result

medium

A. hi hello hello

B. hello hi hello

C. hi hi hi

D. hello hello hi

Solution

1. Step 1: Understand what sub does here

   sub replaces only the first occurrence of 'hello' with 'hi'.

2. Step 2: Apply replacement to the string

   The first 'hello' becomes 'hi', the rest remain unchanged, so the string becomes "hi hello hello".

3. Final Answer:

   hi hello hello -> Option A

4. Quick Check:

   sub replaces first match only [OK]

Hint: sub changes only first match, others stay same [OK]

Common Mistakes:

• Thinking sub replaces all matches
• Confusing output with gsub behavior
• Misreading the string content

4. The following code is intended to replace all occurrences of 'apple' with 'orange' in the string, but it only replaces the first one. What is the error?

fruit = "apple banana apple grape"
new_fruit = fruit.sub('apple', 'orange')
puts new_fruit

medium

A. Use gsub instead of sub to replace all occurrences.

B. The string variable should be an array for replacement.

C. The replacement string must be in double quotes.

D. The method sub does not exist in Ruby.

Solution

1. Step 1: Identify the method used

   The code uses sub, which replaces only the first match.

2. Step 2: Correct method for replacing all matches

   To replace all occurrences, gsub should be used instead of sub.

3. Final Answer:

   Use gsub instead of sub to replace all occurrences. -> Option A

4. Quick Check:

   gsub replaces all matches, sub replaces first only [OK]

Hint: Use gsub for all replacements, sub for first only [OK]

Common Mistakes:

• Using sub when gsub is needed
• Thinking sub works on arrays
• Believing method names are case sensitive differently

5. Given the string "2023-04-01 and 2023-05-01", you want to replace only the month part (the two digits after the first dash) with '12' for all dates. Which Ruby code correctly does this using gsub and a regex?

hard

A. "2023-04-01 and 2023-05-01".sub(/-(\d{2})-/, '-12-')

B. "2023-04-01 and 2023-05-01".gsub(/\d{2}-/, '12-')

C. "2023-04-01 and 2023-05-01".gsub(/-(\d{2})-/, '-12-')

D. "2023-04-01 and 2023-05-01".gsub(/-\d{2}/, '-12')

Solution

1. Step 1: Identify the pattern to replace

   The month is the two digits between dashes, so the regex -(\d{2})- matches the dash, two digits, then dash.

2. Step 2: Use gsub to replace all matches

   Using gsub with the pattern and replacement '-12-' replaces the month part in all dates.

3. Final Answer:

   "2023-04-01 and 2023-05-01".gsub(/-(\d{2})-/, '-12-') -> Option C

4. Quick Check:

   gsub with regex replaces all month parts correctly [OK]

Hint: Use gsub with regex matching month pattern for all replacements [OK]

Common Mistakes:

• Using sub instead of gsub for all matches
• Incorrect regex missing dashes
• Replacing wrong parts of the string