String replacement (${var/old/new}) in Bash Scripting - Time & Space Complexity

Time Complexity: String replacement (${var/old/new})

O(n)

Understanding Time Complexity

We want to understand how the time it takes to replace text inside a string grows as the string gets longer.

How does the replacement operation scale when the input string size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text="hello world hello"
new_text=${text/hello/hi}
echo "$new_text"
    

This code replaces the first occurrence of "hello" with "hi" in the string stored in text.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the string to find the first match of the pattern.
• How many times: The string is checked character by character until the first match is found or the string ends.

How Execution Grows With Input

The time to find the pattern grows roughly with the length of the string because it may need to check each character once.

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

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 grows directly with the length of the string.

Common Mistake

[X] Wrong: "String replacement happens instantly no matter how long the string is."

[OK] Correct: The command must scan the string to find the pattern, so longer strings take more time.

Interview Connect

Knowing how string operations scale helps you write scripts that stay fast even with big inputs.

Self-Check

"What if we replaced all occurrences instead of just the first? How would the time complexity change?"

Practice

1. What does the expression ${var/old/new} do in bash scripting?

easy

A. Appends 'new' to the variable 'var' if it contains 'old'.

B. Replaces the first occurrence of 'old' with 'new' in the variable 'var'.

C. Deletes the variable 'var' if it contains 'old'.

D. Replaces all occurrences of 'old' with 'new' in the variable 'var'.

Solution

1. Step 1: Understand the syntax ${var/old/new}

   This syntax replaces only the first occurrence of the substring 'old' with 'new' inside the variable 'var'.

2. Step 2: Differentiate from ${var//old/new}

   The double slash version replaces all occurrences, but the single slash replaces only the first one.

3. Final Answer:

   Replaces the first occurrence of 'old' with 'new' in the variable 'var'. -> Option B

4. Quick Check:

   Single slash means first occurrence only [OK]

Hint: Single slash replaces first match only, double slash replaces all [OK]

Common Mistakes:

• Confusing single slash with double slash for all replacements
• Thinking it deletes or appends instead of replacing
• Assuming it works on strings outside variables

2. Which of the following is the correct syntax to replace the first occurrence of 'cat' with 'dog' in variable animal?

easy

A. ${animal/cat/dog}

B. ${animal//cat/dog}

C. ${animal/cat|dog}

D. ${animal:cat:dog}

Solution

1. Step 1: Identify correct replacement syntax

   The correct syntax for replacing the first occurrence is ${variable/old/new}, so ${animal/cat/dog} is correct.

2. Step 2: Check other options for errors

   ${animal//cat/dog} uses double slash which replaces all occurrences, not just the first. Options C and D use invalid syntax.

3. Final Answer:

   ${animal/cat/dog} -> Option A

4. Quick Check:

   Single slash correct for first occurrence [OK]

Hint: Use single slash for first replacement, double slash for all [OK]

Common Mistakes:

• Using double slash when only first replacement is needed
• Using wrong delimiters like | or : instead of /
• Confusing syntax with substring extraction

3. Given text="hello world world", what is the output of echo ${text/world/earth}?

medium

A. hello earth earth

B. hello world earth

C. hello earth world

D. hello world world

Solution

1. Step 1: Understand the variable content

   The variable text contains "hello world world" with two 'world' words.

2. Step 2: Apply ${text/world/earth}

   This replaces only the first occurrence of 'world' with 'earth', so the result is "hello earth world".

3. Final Answer:

   hello earth world -> Option C

4. Quick Check:

   Single slash replaces first match only [OK]

Hint: Single slash replaces only first match, so second 'world' stays [OK]

Common Mistakes:

• Expecting all 'world' to change to 'earth'
• Confusing output with original variable
• Misreading variable content

4. What is wrong with this code snippet?

file="data.txt"
newfile=${file/data/txt}
echo $newfile

medium

A. It replaces 'data' with 'txt' correctly.

B. Syntax error due to missing slashes in replacement.

C. It replaces 'data' with 'txt' but misses the dot.

D. It replaces 'data' with 'txt' but changes the file extension incorrectly.

Solution

1. Step 1: Check the replacement syntax

   The replacement syntax must be ${var/old/new} with slashes separating parts. Here, ${file/data/txt} is correct syntax.

2. Step 2: Analyze the replacement effect

   The code replaces 'data' with 'txt', so 'data.txt' becomes 'txt.txt'. There is no syntax error.

3. Step 3: Identify the logical issue

   While the code executes correctly, the replacement of 'data' with 'txt' produces 'txt.txt', which alters the filename in a way that incorrectly impacts the intended file extension handling.

4. Final Answer:

   It replaces 'data' with 'txt' but changes the file extension incorrectly. -> Option D

5. Quick Check:

   Replacement changes 'data' to 'txt', affecting filename [OK]

Hint: Check slashes and replaced parts carefully for syntax and effect [OK]

Common Mistakes:

• Assuming syntax error when slashes are correct
• Ignoring that replacement changes filename parts
• Confusing replacement with substring extraction

5. You have a variable sentence="apple banana apple cherry apple". How do you replace only the second occurrence of 'apple' with 'orange' using bash string replacement?

hard

A. Use parameter expansion with substring and manual replacement.

B. Use ${sentence//apple/orange} to replace all.

C. Use ${sentence/apple/orange} twice.

D. Use ${sentence/apple/orange} once; it replaces second occurrence automatically.

Solution

1. Step 1: Understand limitation of ${var/old/new}

   This syntax replaces only the first occurrence, no direct way to replace the second occurrence.

2. Step 2: Consider manual approach

   To replace the second occurrence, you must split or manipulate the string manually using substring extraction and concatenation.

3. Step 3: Confirm the approach

   Bash parameter expansion with single or double slashes cannot target specific non-first occurrences; manual string manipulation using substrings is required.

4. Final Answer:

   Use parameter expansion with substring and manual replacement. -> Option A

5. Quick Check:

   Only manual substring methods can target second occurrence [OK]

Hint: Single slash replaces first only; second needs manual substring handling [OK]

Common Mistakes:

• Assuming single replacement syntax can target second occurrence
• Using double slash to replace all instead of just second
• Expecting repeated use of ${var/old/new} to replace second occurrence