Substring extraction (${var:offset:length}) in Bash Scripting - Time & Space Complexity

Time Complexity: Substring extraction (${var:offset:length})

O(k)

Understanding Time Complexity

We want to understand how the time it takes to extract a substring changes as the size of the substring or the original string changes.

How does the work grow when we ask for longer parts of the string?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string="Hello, world!"
sub1=${string:0:5}
sub2=${string:7:5}
sub3=${string:0:10}

# Extract different parts of the string

This code extracts parts of a string using the substring syntax: starting at an offset and taking a certain length.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying characters from the original string to create the substring.
• How many times: Once for each character in the substring length.

How Execution Grows With Input

Extracting a substring means copying each character one by one for the requested length.

Input Size (substring length)	Approx. Operations (character copies)
10	10
100	100
1000	1000

Pattern observation: The work grows directly with the length of the substring requested.

Final Time Complexity

Time Complexity: O(k)

This means the time to extract a substring grows linearly with the length of the substring, not the whole string.

Common Mistake

[X] Wrong: "Extracting a substring always takes time proportional to the whole string length."

[OK] Correct: The operation only copies the requested part, so time depends on substring length, not the full string size.

Interview Connect

Knowing how substring extraction scales helps you write efficient scripts and answer questions about string handling in interviews confidently.

Self-Check

"What if we extract multiple substrings in a loop from a very long string? How would the time complexity change?"

Practice

1. What does the expression ${var:2:3} do in bash scripting?

easy

A. Extracts 3 characters from var starting at index 2

B. Extracts 2 characters from var starting at index 3

C. Extracts 3 characters from var starting at index 0

D. Extracts the entire string var ignoring offset and length

Solution

1. Step 1: Understand substring syntax

   The syntax ${var:offset:length} extracts a substring from var starting at offset with length characters.

2. Step 2: Apply to given expression

   Here, offset is 2 and length is 3, so it extracts 3 characters starting from index 2 (0-based).

3. Final Answer:

   Extracts 3 characters from var starting at index 2 -> Option A

4. Quick Check:

   Substring = characters from index 2, length 3 [OK]

Hint: Offset is start index, length is number of chars [OK]

Common Mistakes:

• Confusing offset with length
• Forgetting offset starts at 0
• Assuming length is mandatory

2. Which of the following is the correct syntax to extract 4 characters starting at position 1 from variable text?

easy

A. ${text:1:4}

B. ${text:4:1}

C. ${text:1-4}

D. ${text:1,4}

Solution

1. Step 1: Recall correct substring syntax

   The correct syntax uses colon separators: ${var:offset:length}.

2. Step 2: Match syntax to options

   ${text:1:4} matches this exactly with offset 1 and length 4. Others use invalid separators or wrong order.

3. Final Answer:

   ${text:1:4} -> Option A

4. Quick Check:

   Correct syntax uses colons [OK]

Hint: Use colons, not commas or dashes [OK]

Common Mistakes:

• Using commas or dashes instead of colons
• Swapping offset and length
• Missing braces around variable

3. Given filename="report2024.txt", what is the output of echo ${filename:6:4}?

medium

A. port

B. 2024

C. 202

D. txt

Solution

1. Step 1: Identify substring start and length

   Offset is 6, length is 4. The string is "report2024.txt".

2. Step 2: Extract substring from position 6

   Counting from 0: r(0) e(1) p(2) o(3) r(4) t(5) 2(6) 0(7) 2(8) 4(9). Extract 4 chars starting at index 6: "2024".

3. Final Answer:

   2024 -> Option B

4. Quick Check:

   Substring at 6 length 4 = "2024" [OK]

Hint: Count from zero, then take length chars [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Extracting wrong substring length
• Confusing characters with digits

4. What is wrong with this code snippet?

var="hello world"
echo ${var:5,3}

medium

A. Offset 5 is out of range

B. Length 3 is too large

C. Comma is invalid separator; should use colon

D. Variable name is incorrect

Solution

1. Step 1: Check substring syntax

   The substring syntax requires colons between offset and length, not commas.

2. Step 2: Identify error in code

   The code uses a comma ${var:5,3} which is invalid and causes a syntax error.

3. Final Answer:

   Comma is invalid separator; should use colon -> Option C

4. Quick Check:

   Use colons, not commas [OK]

Hint: Use colons between offset and length [OK]

Common Mistakes:

• Using commas instead of colons
• Assuming offset out of range causes error
• Misnaming variable

5. You have a date string date="2024-06-15". Which command extracts the month part ("06") using substring extraction?

hard

A. ${date:3:2}

B. ${date:6:2}

C. ${date:4:2}

D. ${date:5:2}

Solution

1. Step 1: Locate month position in date string

   The string is "2024-06-15". Counting from 0: 2(0) 0(1) 2(2) 4(3) -(4) 0(5) 6(6) -(7) 1(8) 5(9). Month starts at index 5.

2. Step 2: Extract 2 characters starting at index 5

   Using ${date:5:2} extracts "06" which is the month.

3. Final Answer:

   ${date:5:2} -> Option D

4. Quick Check:

   Month = substring at 5 length 2 [OK]

Hint: Count chars from zero, dash counts as char [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Extracting wrong substring length
• Confusing day and month positions