Character classes ([a-z], [0-9]) in Bash Scripting - Time & Space Complexity

Time Complexity: Character classes ([a-z], [0-9])

O(n)

Understanding Time Complexity

We want to see how the time to run a bash script changes when it uses character classes like [a-z] or [0-9].

How does the script's work grow as the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#!/bin/bash
input="$1"
count=0
for (( i=0; i<${#input}; i++ )); do
  char=${input:i:1}
  if [[ $char =~ [a-z] ]]; then
    ((count++))
  fi
done

echo "Lowercase letters count: $count"
    

This script counts how many lowercase letters are in the input string using the [a-z] character class.

Identify Repeating Operations

• Primary operation: Looping through each character of the input string.
• How many times: Once for every character in the input (length n).

How Execution Grows With Input

Each character is checked once to see if it matches the [a-z] pattern.

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 directly with the input size. Double the input, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the script takes time proportional to the length of the input string.

Common Mistake

[X] Wrong: "Using character classes like [a-z] makes the script slower in a way that depends on the number of matches."

[OK] Correct: The script checks each character once regardless of matches, so time depends only on input length, not how many characters match.

Interview Connect

Understanding how pattern matching scales helps you write efficient scripts and explain your reasoning clearly in interviews.

Self-Check

"What if we changed the script to check for multiple character classes inside the loop? How would the time complexity change?"

Practice

1. What does the character class [a-z] match in bash scripting?

easy

A. All lowercase letters from a to z

B. All uppercase letters from A to Z

C. All digits from 0 to 9

D. All special characters

Solution

1. Step 1: Understand character class notation

   The notation [a-z] means any character from 'a' to 'z' in lowercase.

2. Step 2: Identify what [a-z] matches

   This matches all lowercase letters, not uppercase letters, digits, or special characters.

3. Final Answer:

   All lowercase letters from a to z -> Option A

4. Quick Check:

   [a-z] = lowercase letters [OK]

Hint: Remember: a-z means lowercase letters only [OK]

Common Mistakes:

• Confusing lowercase with uppercase letters
• Thinking it matches digits
• Assuming it matches special characters

2. Which of the following is the correct syntax to match any digit using a character class in bash?

easy

A. [9-0]

B. [a-z]

C. [A-Z]

D. [0-9]

Solution

1. Step 1: Identify digit matching syntax

   The character class [0-9] matches any digit from 0 to 9.

2. Step 2: Check other options

   [a-z] matches lowercase letters, [A-Z] matches uppercase letters, and [9-0] is invalid because ranges must go from lower to higher.

3. Final Answer:

   [0-9] -> Option D

4. Quick Check:

   [0-9] = digits [OK]

Hint: Digits always use [0-9], not reversed ranges [OK]

Common Mistakes:

• Using reversed ranges like [9-0]
• Confusing letters with digits
• Using uppercase letter ranges for digits

3. What will be the output of this command?

echo -e "a1 b2 c3" | grep -o '[a-z][0-9]'

medium

A. a1 b2 c3

B. a1
b2
c3

C. a b c

D. 1 2 3

Solution

1. Step 1: Understand the grep command with -o and pattern

   The pattern [a-z][0-9] matches a lowercase letter followed by a digit. The -o option prints each match on a new line.

2. Step 2: Apply pattern to input string

   Input "a1 b2 c3" contains matches: "a1", "b2", and "c3". Each will be printed on its own line.

3. Final Answer:

   a1 b2 c3 -> Option B

4. Quick Check:

   Pattern matches pairs, -o prints each on new line [OK]

Hint: Use -o to print each match on a separate line [OK]

Common Mistakes:

• Expecting all matches on one line
• Matching letters or digits alone
• Ignoring the -o option effect

4. Identify the error in this grep command:

grep '[a-z-9]' file.txt

medium

A. Should use double brackets [[ ]] instead of single brackets

B. Missing quotes around the pattern

C. The character class is invalid because of the dash placement

D. No error, command is correct

Solution

1. Step 1: Analyze the character class syntax

   The pattern [a-z-9] is intended to match letters and digits, but the dash is misplaced between 'z' and '9'.

2. Step 2: Understand dash usage in character classes

   Dash (-) defines a range if placed between two characters. Here, 'z-9' is invalid because 'z' comes after '9' in ASCII order. Dash should be first or last to be literal.

3. Final Answer:

   The character class is invalid because of the dash placement -> Option C

4. Quick Check:

   Dash in ranges must go from lower to higher [OK]

Hint: Put dash at start or end to avoid range errors [OK]

Common Mistakes:

• Placing dash between characters in wrong order
• Confusing quotes usage
• Using wrong bracket types

5. You want to extract all words from a file that contain only lowercase letters and digits. Which grep pattern correctly matches such words?

grep -E '\b[?]+\b' file.txt

Choose the correct pattern to replace ?.

hard

A. [a-z0-9]+

B. [a-z]+[0-9]+

C. [a-z][0-9]

D. [0-9a-z]{2,}

Solution

1. Step 1: Understand the requirement for matching words

   We want words with only lowercase letters and digits, any order, any length (at least one character).

2. Step 2: Analyze each pattern

   [a-z0-9]+ matches one or more lowercase letters or digits in any order.
   [a-z]+[0-9]+ requires letters followed by digits only.
   [a-z][0-9] matches exactly two characters: one letter then one digit.
   [0-9a-z]{2,} matches two or more letters/digits but order is not enforced; this is valid but less clear than [a-z0-9]+.

3. Final Answer:

   [a-z0-9]+ -> Option A

4. Quick Check:

   Character class with + matches any length words [OK]

Hint: Use [a-z0-9]+ to match letters and digits in any order [OK]

Common Mistakes:

• Forcing letters then digits order
• Matching only two characters
• Ignoring word boundaries