String Traversal and Character Access in DSA Java - Time & Space Complexity

Time Complexity: String Traversal and Character Access

O(n)

Understanding Time Complexity

We want to understand how long it takes to look at each letter in a word or sentence.

How does the time grow when the word gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

String text = "hello";
for (int i = 0; i < text.length(); i++) {
    char c = text.charAt(i);
    System.out.print(c + " ");
}
    

This code goes through each letter in the string and prints it out.

Identify Repeating Operations

• Primary operation: Accessing each character in the string one by one.
• How many times: Once for every character in the string.

How Execution Grows With Input

As the string gets longer, the number of steps grows the same way.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the string length.

Common Mistake

[X] Wrong: "Accessing each character is instant no matter the string size."

[OK] Correct: Each character must be checked one by one, so longer strings take more time.

Interview Connect

Knowing how string traversal time grows helps you write clear and efficient code when working with text data.

Self-Check

"What if we used nested loops to compare every character with every other character? How would the time complexity change?"

Practice

1. What does the charAt() method do when used on a Java String?

easy

A. Returns the character at a specified index in the string

B. Returns the length of the string

C. Converts the string to uppercase

D. Splits the string into an array of substrings

Solution

1. Step 1: Understand the purpose of charAt()

   The charAt() method is designed to access a single character at a given index in a string.

2. Step 2: Compare with other string methods

   Methods like length() return the string length, toUpperCase() changes case, and split() divides the string. These are different from charAt().

3. Final Answer:

   Returns the character at a specified index in the string -> Option A

4. Quick Check:

   charAt() = character access [OK]

Hint: Remember: charAt gets one character by index [OK]

Common Mistakes:

• Confusing charAt() with length()
• Thinking charAt() splits the string
• Assuming charAt() changes string case

2. Which of the following is the correct way to loop through each character of a string str in Java?

easy

A. for (int i = 1; i < str.length(); i++) { char c = str.charAt(i); }

B. for (int i = 0; i <= str.length(); i++) { char c = str.charAt(i); }

C. for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); }

D. for (int i = 1; i <= str.length(); i++) { char c = str.charAt(i); }

Solution

1. Step 1: Understand string indexing in Java

   String indices start at 0 and go up to length - 1. So loop must run from 0 to less than length.

2. Step 2: Check loop conditions

   for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); } uses i < str.length(), which correctly stops before index equals length. Options B and D use <= which causes out-of-bounds error. Options C and D start at 1, skipping first character.

3. Final Answer:

   for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); } -> Option C

4. Quick Check:

   Loop from 0 to length-1 [OK]

Hint: Loop from 0 to length-1 for string indices [OK]

Common Mistakes:

• Using <= instead of < causing index error
• Starting loop at 1 skipping first char
• Confusing string length with last index

3. What is the output of the following Java code?

String s = "hello";
for (int i = 0; i < s.length(); i++) {
  if (i % 2 == 0) {
    System.out.print(s.charAt(i));
  }
}

medium

A. hello

B. hlo

C. el

D. heo

Solution

1. Step 1: Identify loop and condition

   The loop runs from i=0 to 4 (length 5). It prints characters only when i is even (0,2,4).

2. Step 2: Find characters at even indices

   Index 0: 'h', Index 2: 'l', Index 4: 'o'. These characters are printed in order.

3. Final Answer:

   hlo -> Option B

4. Quick Check:

   Even indices chars = hlo [OK]

Hint: Print chars at even indices only [OK]

Common Mistakes:

• Printing all characters ignoring condition
• Confusing even and odd indices
• Off-by-one errors in loop

4. Consider this Java code snippet:

String text = "abc";
for (int i = 0; i <= text.length(); i++) {
  System.out.print(text.charAt(i));
}

What error will occur when running this code?

medium

A. StringIndexOutOfBoundsException

B. ArrayIndexOutOfBoundsException

C. NullPointerException

D. No error, prints 'abc'

Solution

1. Step 1: Analyze loop bounds

   The loop runs from i=0 to i=3 (because of <= and length=3). Valid indices are 0,1,2 only.

2. Step 2: Identify error cause

   At i=3, charAt(3) is called, which is out of string bounds, causing StringIndexOutOfBoundsException.

3. Final Answer:

   StringIndexOutOfBoundsException -> Option A

4. Quick Check:

   charAt index out of range causes StringIndexOutOfBoundsException [OK]

Hint: Loop must use < length, not <= length [OK]

Common Mistakes:

• Confusing StringIndexOutOfBoundsException with ArrayIndexOutOfBoundsException
• Assuming no error occurs
• Thinking NullPointerException will happen

5. Given the string input = "a1b2c3d4", which code snippet correctly extracts and prints only the digits in order?

hard

A. for (int i = 0; i < input.length(); i++) { if (Character.isLetter(input.charAt(i))) System.out.print(input.charAt(i)); }

B. for (int i = 0; i < input.length(); i++) { if (input.charAt(i) >= 'a' && input.charAt(i) <= 'z') System.out.print(input.charAt(i)); }

C. for (int i = 0; i < input.length(); i++) { System.out.print(input.charAt(i)); }

D. for (int i = 0; i < input.length(); i++) { if (input.charAt(i) >= '0' && input.charAt(i) <= '9') System.out.print(input.charAt(i)); }

Solution

1. Step 1: Understand the goal

   We want to print only digits from the string, ignoring letters.

2. Step 2: Check each option's condition

   for (int i = 0; i < input.length(); i++) { if (Character.isLetter(input.charAt(i))) System.out.print(input.charAt(i)); } uses Character.isLetter(), prints letters. for (int i = 0; i < input.length(); i++) { if (input.charAt(i) >= 'a' && input.charAt(i) <= 'z') System.out.print(input.charAt(i)); } checks lowercase letters range, prints letters. for (int i = 0; i < input.length(); i++) { System.out.print(input.charAt(i)); } prints all characters. for (int i = 0; i < input.length(); i++) { if (input.charAt(i) >= '0' && input.charAt(i) <= '9') System.out.print(input.charAt(i)); } checks if char between '0' and '9', prints "1234" correctly.

3. Final Answer:

   for (int i = 0; i < input.length(); i++) { if (input.charAt(i) >= '0' && input.charAt(i) <= '9') System.out.print(input.charAt(i)); } -> Option D

4. Quick Check:

   Check char between '0' and '9' to find digits [OK]

Hint: Check if char is between '0' and '9' for digits [OK]

Common Mistakes:

• Printing letters instead of digits
• Printing all characters without filtering
• Using wrong character range for digits