String prefix removal (${var#pattern}) in Bash Scripting - Time & Space Complexity

Time Complexity: String prefix removal (${var#pattern})

O(n)

Understanding Time Complexity

We want to understand how the time it takes to remove a prefix from a string grows as the string gets longer.

Specifically, how does the operation ${var#pattern} behave when the input string changes size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string="hello_world_example"
pattern="hello_"
result=${string#${pattern}}
echo "$result"
    

This code removes the shortest matching prefix pattern from the string variable.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The shell checks characters from the start of the string to find the pattern match.
• How many times: It compares characters one by one until the pattern is matched or no match is found.

How Execution Grows With Input

As the string length grows, the shell compares more characters to find the prefix pattern.

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

Pattern observation: The number of character comparisons grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to remove the prefix grows linearly with the length of the string.

Common Mistake

[X] Wrong: "Removing a prefix is always instant, no matter the string size."

[OK] Correct: The shell must check characters one by one to find the pattern, so longer strings take more time.

Interview Connect

Understanding how simple string operations scale helps you reason about script performance and avoid surprises in real tasks.

Self-Check

"What if we used the longest match removal syntax (${var##pattern}) instead? How would the time complexity change?"

Practice

1. What does the Bash expression ${var#pattern} do?

easy

A. Removes the shortest matching prefix pattern from the variable's value

B. Removes the longest matching suffix pattern from the variable's value

C. Removes the shortest matching suffix pattern from the variable's value

D. Removes the longest matching prefix pattern from the variable's value

Solution

1. Step 1: Understand the syntax

   The syntax ${var#pattern} is used in Bash to remove a prefix pattern from the start of the variable's value.

2. Step 2: Identify shortest prefix removal

   The single # removes the shortest matching prefix, unlike ## which removes the longest.

3. Final Answer:

   Removes the shortest matching prefix pattern from the variable's value -> Option A

4. Quick Check:

   Prefix removal = shortest match = A [OK]

Hint: Single # removes shortest prefix, double ## removes longest [OK]

Common Mistakes:

• Confusing # with ## for prefix length
• Mixing prefix removal with suffix removal
• Thinking it removes suffix instead of prefix

2. Which of the following is the correct syntax to remove the shortest prefix matching abc from variable var in Bash?

easy

A. ${var#abc}

B. ${var##abc}

C. ${var%abc}

D. ${var%%abc}

Solution

1. Step 1: Recall prefix removal syntax

   Single # removes shortest prefix, double ## removes longest prefix. % and %% remove suffixes.

2. Step 2: Match the pattern

   To remove shortest prefix matching 'abc', use ${var#abc}.

3. Final Answer:

   ${var#abc} -> Option A

4. Quick Check:

   Shortest prefix removal = single # = B [OK]

Hint: Use single # for shortest prefix removal syntax [OK]

Common Mistakes:

• Using ## instead of # for shortest prefix
• Using % or %% which remove suffixes
• Confusing prefix and suffix removal syntax

3. Given var="folder/subfolder/file.txt", what is the output of echo ${var#*/}?

medium

A. folder/subfolder/file.txt

B. subfolder/file.txt

C. file.txt

D. folder

Solution

1. Step 1: Understand the pattern */

   The pattern */ matches the shortest prefix ending with a slash.

2. Step 2: Remove shortest prefix matching */

   From "folder/subfolder/file.txt", the shortest prefix matching */ is "folder/". Removing it leaves "subfolder/file.txt".

3. Final Answer:

   subfolder/file.txt -> Option B

4. Quick Check:

   Remove shortest prefix ending with / = subfolder/file.txt [OK]

Hint: Pattern */ removes up to first slash [OK]

Common Mistakes:

• Removing longest prefix with ## instead of #
• Expecting only filename instead of subfolder/file.txt
• Confusing prefix removal with suffix removal

4. Consider the script snippet:

var="abc123abc456"
echo ${var##abc*}

It outputs an empty line. Why?

medium

A. Because the pattern is invalid and causes an error

B. Because abc* matches the entire string as shortest prefix

C. Because abc* matches the longest prefix, so nothing remains

D. Because the variable is empty

Solution

1. Step 1: Analyze the pattern abc*

   The pattern abc* matches 'abc' followed by zero or more any characters.

2. Step 2: Understand longest prefix removal

   With ##, it removes the longest matching prefix. The * matches greedily as many characters as possible after 'abc', so the match covers the entire string.

3. Final Answer:

   Because abc* matches the longest prefix, so nothing remains -> Option C

4. Quick Check:

   Longest prefix with ## + greedy * = B [OK]

Hint: Wildcard * matches greedily with longest prefix ## [OK]

Common Mistakes:

• Confusing ## (longest) with # (shortest)
• Underestimating greedy nature of * in longest match
• Assuming pattern causes error or variable is empty

5. You have a variable path="folder/home/user/docs/report.txt". Which command removes only the first slash and everything before it, leaving home/user/docs/report.txt?

hard

A. echo ${path#/*}

B. echo ${path##/*}

C. echo ${path##*/}

D. echo ${path#*/}

Solution

1. Step 1: Understand the variable value

   The variable path is "folder/home/user/docs/report.txt".

2. Step 2: Analyze each option's pattern

   ${path#/*} removes shortest prefix matching slash followed by anything, but path doesn't start with /, so no match.
   ${path##/*} removes longest prefix matching slash-anything, no match.
   ${path##*/} removes longest prefix up to last slash, leaving only filename "report.txt".
   ${path#*/} removes shortest prefix up to first slash ("folder/"), leaving "home/user/docs/report.txt".

3. Step 3: Choose correct option

   To remove up to the first slash, use ${path#*/}.

4. Final Answer:

   echo ${path#*/} -> Option D

5. Quick Check:

   Remove shortest prefix up to first slash = D [OK]

Hint: Use #*/ to remove up to first slash only [OK]

Common Mistakes:

• Using ##*/ removes up to last slash (only filename)
• Using #/* or ##/* which don't match without leading slash
• Confusing prefix removal with suffix removal