Capture groups in Bash in Bash Scripting - Time & Space Complexity

Time Complexity: Capture groups in Bash

O(n)

Understanding Time Complexity

We want to understand how the time taken by a Bash script using capture groups changes as the input size grows.

Specifically, how does the script's work increase when processing longer text or more matches?

Scenario Under Consideration

Analyze the time complexity of the following Bash snippet using capture groups.

text="apple banana cherry date"

for word in $text; do
  if [[ $word =~ (a)(.*) ]]; then
    echo "First letter: ${BASH_REMATCH[1]}, Rest: ${BASH_REMATCH[2]}"
  fi
done
    

This code loops over words in a string and uses capture groups to split each word starting with 'a' into parts.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: Looping over each word in the text.
• How many times: Once for each word in the input string.

How Execution Grows With Input

As the number of words grows, the script checks each word once.

Input Size (n)	Approx. Operations
10	10 checks and possible captures
100	100 checks and possible captures
1000	1000 checks and possible captures

Pattern observation: The work grows directly with the number of words.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of words processed.

Common Mistake

[X] Wrong: "Capture groups make the script slower exponentially because they do extra work inside the loop."

[OK] Correct: Each capture group operation happens once per word, so it adds a small constant cost per iteration, not exponential growth.

Interview Connect

Understanding how loops and pattern matching scale helps you explain script efficiency clearly and confidently.

Self-Check

"What if the script used nested loops to process each character inside each word? How would the time complexity change?"

Practice

1. What does the BASH_REMATCH array hold after a successful regex match in Bash?

easy

A. The full matched string at index 0 and captured groups from index 1 onwards

B. Only the captured groups without the full match

C. The regex pattern used for matching

D. The exit status of the last command

Solution

1. Step 1: Understand BASH_REMATCH usage

   When using [[ string =~ regex ]], Bash stores the full matched text in BASH_REMATCH[0].

2. Step 2: Identify captured groups storage

   Captured groups from parentheses in the regex are stored starting at BASH_REMATCH[1] onwards.

3. Final Answer:

   The full matched string at index 0 and captured groups from index 1 onwards -> Option A

4. Quick Check:

   BASH_REMATCH = full match + groups [OK]

Hint: Remember index 0 is full match, groups start at 1 [OK]

Common Mistakes:

• Thinking BASH_REMATCH holds only groups
• Confusing BASH_REMATCH with exit status
• Expecting regex pattern in BASH_REMATCH

2. Which of the following is the correct syntax to test if a string matches a regex and capture groups in Bash?

easy

A. match $string $regex

B. if ($string =~ $regex); then

C. [[ $string =~ $regex ]]

D. test $string =~ $regex

Solution

1. Step 1: Recall Bash regex match syntax

   Bash uses the conditional expression [[ string =~ regex ]] to test regex matches.

2. Step 2: Identify correct syntax among options

   Only [[ $string =~ $regex ]] uses the correct Bash syntax with double brackets and the =~ operator.

3. Final Answer:

   [[ $string =~ $regex ]] -> Option C

4. Quick Check:

   Use [[ ]] with =~ for regex match [OK]

Hint: Use double brackets [[ ]] with =~ for regex matching [OK]

Common Mistakes:

• Using single brackets [ ] which don't support =~
• Using parentheses () like in other languages
• Using commands like test or match incorrectly

3. What will be the output of this Bash script?

string="user:1234"
if [[ $string =~ ([a-z]+):([0-9]+) ]]; then
  echo "Name=${BASH_REMATCH[1]}, ID=${BASH_REMATCH[2]}"
fi

medium

A. Name=user, ID=1234

B. Name=user:1234, ID=

C. Name=, ID=

D. Syntax error

Solution

1. Step 1: Analyze regex and string

   The regex ([a-z]+):([0-9]+) matches letters before colon and digits after colon in the string "user:1234".

2. Step 2: Check captured groups in BASH_REMATCH

   BASH_REMATCH[1] captures "user" and BASH_REMATCH[2] captures "1234".

3. Final Answer:

   Name=user, ID=1234 -> Option A

4. Quick Check:

   Captured groups print correct values [OK]

Hint: Captured groups appear in BASH_REMATCH starting at index 1 [OK]

Common Mistakes:

• Expecting full string in BASH_REMATCH[1]
• Forgetting to use double brackets [[ ]]
• Misreading regex pattern

4. Identify the error in this Bash snippet:

string="abc123"
if [[$string =~ ([a-z]+)([0-9]+)]]; then
  echo "${BASH_REMATCH[1]} and ${BASH_REMATCH[2]}"
fi

medium

A. Regex pattern is invalid

B. Missing spaces inside [[ and ]]

C. BASH_REMATCH is not set by =~ operator

D. Using single brackets instead of double brackets

Solution

1. Step 1: Check syntax of conditional expression

   The conditional expression [[ ... ]] requires spaces after [[ and before ]]. The snippet misses spaces.

2. Step 2: Confirm regex and BASH_REMATCH usage

   The regex is valid and BASH_REMATCH is set correctly when using =~ inside [[ ]].

3. Final Answer:

   Missing spaces inside [[ and ]] -> Option B

4. Quick Check:

   Spaces needed inside [[ and ]] [OK]

Hint: Always put spaces after [[ and before ]] [OK]

Common Mistakes:

• Omitting spaces inside [[ ]]
• Confusing single [ ] with [[ ]]
• Assuming regex pattern is wrong

5. You want to extract the domain and path from a URL string in Bash using capture groups. Which regex and code snippet correctly captures domain and path?

url="https://example.com/path/to/page"
if [[ $url =~ https://([^/]+)(/.*) ]]; then
  echo "Domain: ${BASH_REMATCH[1]}"
  echo "Path: ${BASH_REMATCH[2]}"
fi

hard

A. Captures domain and path but misses https:// prefix

B. BASH_REMATCH does not support multiple groups

C. Fails because regex does not escape dots

D. Correctly captures domain as example.com and path as /path/to/page

Solution

1. Step 1: Analyze regex pattern

   The regex https://([^/]+)(/.*) matches 'https://' literally, then captures domain (any chars except '/') and path (slash followed by anything).

2. Step 2: Check BASH_REMATCH usage

   BASH_REMATCH[1] holds domain, BASH_REMATCH[2] holds path, correctly extracted from the URL.

3. Final Answer:

   Correctly captures domain as example.com and path as /path/to/page -> Option D

4. Quick Check:

   Regex groups extract domain and path correctly [OK]

Hint: Use ([^/]+) for domain and (/.*) for path [OK]

Common Mistakes:

• Not escaping dots in regex (not needed inside character class)
• Assuming BASH_REMATCH can't hold multiple groups
• Missing literal https:// in regex